The Regularity Method and Problems in Extremal Combinatorics

点击翻译按钮获取中文摘要

ABSTRACTPrincipal Investigator: Rodl, Vojtech Proposal Number: DMS - 0800070Institution: Emory UniversityTitle: The Regularity Method and Problems in Extremal CombinatoricsThe PI proposes research in the area of discrete mathematics with emphasis on Ramsey theory and extremal and probabilistic combinatorics. The project seeks further development of the Regularity Method that has had many successes over the past 30 years, and applications of the method to a variety of problems in extremal combinatorics and Ramsey theory. The PI also plans to use methods of probabilistic combinatorics to attack some older problems in Ramsey theory. In the area of quasi-randomness, one of the PI's long-term projects is to investigate the properties of quasi-random sparse graphs and uniform hypergraphs.Over the last two decades, the use of probability has become one of the most powerful tools in discrete mathematics and computer science. The understanding of discrete, combinatorial structures is very important in modern science and technology. For instance, probabilistic reasoning is crucial for the design of large networks and algorithms. In discrete mathematics, one of the most successful techniques is the probabilistic method, which enables one to prove results about deterministic objects. One of the more recent techniques employs the idea of quasi-randomness. Quasi-random properties that enable one to find and enumerate sub-objects of a given type are of particular interest. The main part of this proposal aims to extend the applicability of the current techniques to a broader class of combinatorial structures. The results should lead to applications in various areas such as phase transition, game theory or theoretical computer science.