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授予的摘要旨在加深我们对伴随秩序的理解（Ramsey理论研究）和随机疾病（由Quasi-random Techniques进行了研究）。 它的目标之一是在离散结构中查找和枚举指定的子对象的收集的征收有效方法。 该项目寻求一种方法论 - 规律性方法 - 在过去的25年中取得了一系列惊人的成功，并在极端组合和拉姆西理论中涉及各种问题的方法。 在准随机性领域，Pi's-slong项目之一是研究准随机图和均匀超图的性质。 特别是，PI对扩展规律方法的适用性感兴趣。在现代科学和技术中，对离散，组合结构的理解非常重要。 例如，概率推理对于大型网络和OF算法的设计至关重要。 在离散的数学中，最成功的技术之一是概率方法，它使人们能够谚语介绍确定性对象。 最近的技术之一是使用准随机性的想法。 准随机物体是一个对象，它与许多其他类型的其他对象共享多个属性。 可以使给定类型的sub-objjects的准随机属性特别有趣。该提案的主要部分旨在将当前技术的功能扩展到更广泛的组合结构。 结果应导致不同的应用程序的应用，从相变和游戏理论到理论计算机科学。