The Regularity Method and Problems in Extremal Combinatorics

主要研究者：Rodl，Vojtech 提案编号：DMS -0800070机构：埃默里大学标题：极值组合学中的正则性方法和问题PI提出了离散数学领域的研究，重点是拉姆齐理论和极值和概率组合学。该项目旨在进一步发展在过去30年中取得了许多成功的正则方法，并将该方法应用于极值组合学和拉姆齐理论中的各种问题。PI还计划使用概率组合学的方法来解决拉姆齐理论中的一些老问题。在准随机性领域，PI的长期项目之一是研究准随机稀疏图和一致超图的性质。在过去的二十年里，概率的使用已经成为离散数学和计算机科学中最强大的工具之一。对离散组合结构的理解在现代科学技术中非常重要。例如，概率推理对于大型网络和算法的设计至关重要。在离散数学中，最成功的技术之一是概率方法，它使人们能够证明关于确定性对象的结果。最近的一种技术采用了准随机性的思想。使人们能够找到和枚举给定类型的子对象的准随机属性是特别感兴趣的。该提案的主要部分旨在将当前技术的适用性扩展到更广泛的组合结构类。结果应该导致在各个领域的应用，如相变，博弈论或理论计算机科学。

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.