The Regularity Method for Sparse Graphs and Hypergraphs

这个建议寻求进一步发展和理解的正则性方法，这已经有一系列的成功离散数学。证明了E. Szemerédi for graphs断言，每个稠密图都可以分解为相对较少的类随机子图。这种类似随机的行为使人们能够找到并枚举给定同构类型的子图。这个观测被称为计数引理。Szemerédi的正则性引理和计数引理的相互作用，被称为稠密图的正则性方法，在极值图论领域有许多应用。由于给定边密度的随机图通常比任意相同边密度的图更容易分析，正则性方法使我们能够将一些适用于随机图的方法转移到所有图的类中。近年来，正则性方法部分扩展到新类型的离散结构：稀疏图和k-一致超图。特别是，类似物的正则引理，这些组合对象的建立。在建议的程序中，我们寻求更深入的了解这些正则引理保证的类随机行为。此外，我们专注于这些新技术在极值组合学领域的应用。

This proposal seeks further development and understanding of the Regularity Method, which has had a series of successes in Discrete Mathematics. The Regularity Lemma of E. Szemerédi for graphs asserts that every dense graph can be decomposed into relatively few random-like subgraphs. This random-like behavior enables one to find and enumerate subgraphs of a given isomorphism type. This observation is called Counting Lemma. The interplay of Szemerédi's Regularity Lemma and the Counting Lemma, referred to as the Regularity Method for dense graphs, has many applications in the area ot extremal graph theory. Since random graphs of a given edge-density are usually easier to analyze than arbitrary graphs of the same edge-density, the Regularity Method enables us to transfer some methods applicable to random graphs to the class of all graphs. In recent years the Regularity Method was partly expanded to new types of discrete structures: sparse graphs and k-uniform hypergraphs. In particular, analogues of the Regularity Lemma for these combinatorial objects were established. In the proposed program, we seek a deeper understanding of the random-like behavior guaranteed by those Regularity Lemmas. Furthermore, we focus on applications of these novel techniques in the area of extremal combinatorics.