Quasi-randomness and The Regularity Lemma

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

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.