Randomness and Quasi-randomness of Graphs and Set Systems

图和集合系统的随机性和拟随机性

• 批准号: 0300529
• 负责人: Vojtech Rodl
• 金额: $ 34.66万
• 依托单位: Emory University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-08-01 至 2009-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0300529&HistoricalAwards=false
• 关键词: Randomness; Quasi; randomness; Graphs; Set

Abstract for award of Rodl 0300529The proposed research aims at deepening our understanding ofspontaneous order (studied in Ramsey theory) and of random disorder(investigated by quasi-random techniques). One of its goals is todesign efficient methods for finding and enumerating collections ofspecified sub-objects in discrete structures. The project seeksfurther development of a methodology - the Regularity Method - thathas had a series of striking successes over the past 25 years, and toapply the method to a variety of problems in extremal combinatoricsand Ramsey theory. In the area of quasi-randomness, one of the PI'slong-term projects is to investigate the properties of quasi-randomsparse graphs and uniform hypergraphs. In particular, the PI isinterested in extending the applicability of the Regularity Method tothese structures.The understanding of discrete, combinatorial structures is veryimportant in modern science and technology. For instance,probabilistic reasoning is crucial in the design of large networks andof algorithms. In discrete mathematics, one of the most successfultechniques is the probabilistic method, which enables one to proveresults about deterministic objects. One of the more recenttechniques employs the idea of quasi-randomness. A quasi-randomobject is an object that shares several properties with many otherobjects of the same kind. Quasi-random properties that enable one to find and enumerate sub-objects of a given type are of particularinterest. The main part of this proposal aims to extend theapplicability of the current techniques to a broader class of combinatorialstructures. The results should lead to applications in differentareas, ranging from phase transition and game theory to theoreticalcomputer science.

Rodl 获奖摘要 0300529 所提出的研究旨在加深我们对自发秩序（在拉姆齐理论中研究）和随机无序（通过准随机技术研究）的理解。 其目标之一是设计有效的方法来查找和枚举离散结构中指定子对象的集合。 该项目寻求进一步发展一种方法——正则方法——该方法在过去 25 年中取得了一系列惊人的成功，并将该方法应用于极值组合学和拉姆齐理论中的各种问题。 在准随机性领域，PI 的长期项目之一是研究准随机稀疏图和均匀超图的性质。 特别是，PI 有兴趣将正则方法的适用性扩展到这些结构。对离散组合结构的理解在现代科学技术中非常重要。 例如，概率推理在大型网络和算法的设计中至关重要。 在离散数学中，最成功的技术之一是概率方法，它使人们能够证明有关确定性对象的结果。 最近的技术之一采用了准随机性的概念。 准随机对象是与许多其他同类对象共享多个属性的对象。 使人们能够查找和枚举给定类型的子对象的准随机属性特别令人感兴趣。该提案的主要部分旨在将当前技术的适用性扩展到更广泛的组合结构。 研究结果应该能够在不同领域得到应用，从相变和博弈论到理论计算机科学。