Randomness and Quasi-randomness of Graphs and Set Systems

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

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.