The Regularity Method for Sparse Graphs and Hypergraphs

• Applicant: Professor Dr. Mathias Schacht
• Subject Area: Mathematics
• Term: from 2005 to 2008
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5443326

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.

• DFG Programme: Research Grants