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 -0800070INCTITITION：Emory UniversityTitle：极端组合中的规则性方法和问题PI在离散数学领域提出了研究，重点是Ramsey理论以及Ramsey理论以及概念性和概念性结合剂。该项目寻求进一步发展的规律性方法，该方法在过去30年中取得了许多成功，并将该方法应用于极端组合和拉姆西理论中的各种问题。 PI还计划使用概率组合学的方法来攻击拉姆西理论中的一些旧问题。在准随机性领域，PI的长期项目之一是研究准随机稀疏图和统一的超图的特性。从过去的二十年中，概率的使用已成为最强大的工具之一离散数学和计算机科学。在现代科学和技术中，对离散，组合结构的理解非常重要。例如，概率推理对于大型网络和算法的设计至关重要。在离散数学中，最成功的技术之一是概率方法，它使人们能够证明有关确定对象的结果。最近的技术之一采用了准随机性的想法。使给定类型的属于并枚举的子对象的准随机属性特别感兴趣。该提案的主要部分旨在将当前技术的适用性扩展到更广泛的组合结构。结果应导致在各个领域的应用，例如相变，游戏理论或理论计算机科学。