Quasi-randomness and The Regularity Lemma

由Paul Erdos首创并主要发展的概率方法已成为组合数学中最有力的工具之一。在随机图和其他组合结构的研究中已经进行了广泛的研究，其动机通常是需要证明某些组合对象的存在的应用。这个项目面向这个蓬勃发展的领域，在这个领域，概率推理在确定性陈述的证明中起着至关重要的作用。最著名的例子之一是Szmeredi的正则性引理。这个引理允许人们将任何图分解成分量，这些分量的准随机性确保了某些子结构的存在，就像它们是随机对象一样。基于正则性引理的证明方法在图论和理论计算机科学中已经有了大量的应用。最近，这些技术中的一些已经扩展到稀疏图(原来的正则性引理不能应用于稀疏图)以及一些集合系统。首席调查员计划对这些技术进行系统研究。

The probabilistic method pioneered and chiefly developed by Paul Erdos has become one of the most powerful tools in combinatorics. Extensive research has been carried out in the study of random graphs and other combinatorial structures, often motivated by applications requiring the proof of existence of certain combinatorial objects. This project is oriented to this vigorously developing area in which probabilistic reasoning plays a crucial role in the proof of deterministic statements. One of the most notable examples is the Regularity Lemma of Szemeredi. This lemma allows one to decompose any graph into components whose quasi-randomness ensures the existence of certain substructures, as though they were random objects. Proof methods based on the Regularity Lemma already have numerous applications in graph theory and theoretical computer science. Recently, some of these techniques have been extended to sparse graphs (to which the original regularity lemma could not be applied) as well as to some set systems. The Principal Investigator plans systematic study of such techniques.