The Regularity Method and Problems in Extremal Combinatorics

主要调查者：Rodl，Vojtech建议编号：DMS-0800070机构：Emory University标题：极值组合中的正则性方法和问题PI建议在离散数学领域进行研究，重点是Ramsey理论和极值和概率组合学。该项目寻求进一步发展在过去30年中取得了许多成功的正则性方法，并将该方法应用于极值组合学和Ramsey理论中的各种问题。PI还计划使用概率组合学的方法来解决Ramsey理论中的一些较老的问题。在准随机性领域，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.