The Regularity Method and Problems in Extremal Combinatorics

极值组合学中的正则方法及问题

• 批准号: 0800070
• 负责人: Vojtech Rodl
• 金额: $ 36.89万
• 依托单位: Emory University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-06-01 至 2014-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0800070&HistoricalAwards=false
• 关键词: Regularity; Method; Problems; 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.

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