The ACO Seminar (2012-2013)

Szemeredi's regularity lemma is one of the most important tools in extremal graph theory. Roughly speaking, it says that the vertex set of every graph may be divided into a bounded number of parts in such a way that most of the induced bipartite graphs between different parts are pseudo-random. Often the strength of the regularity lemma lies in the fact that it may be combined with a counting or embedding lemma that tells us approximately how many copies of a particular subgraph a graph contains, in terms of the densities arising in a regular partition.

For sparse graphs, the regularity lemma of Szemeredi is vacuous, since every equipartition into a bounded number of parts is regular. It was observed independently by Kohayakawa and Rodl that the regularity lemma can nevertheless be generalized to a large class of graphs with density tending to zero. Unfortunately, there is a fundamental difficulty with finding a sparse counting or embedding lemma to match a sparse regularity lemma. The natural hoped-for sparse embedding lemma is false and there are counterexamples to it whose edge density tends to zero arbitrarily slowly. In 1994, Kohayakawa, Luczak, and Rodl conjectured that graphs for which the sparse embedding lemma fails should be extremely rare. We prove this conjecture in the case when the embedded graph is 2-balanced (this class includes many natural graphs, e.g., cliques and cycles). We also prove its natural stronger variant of the KLR conjecture which is sufficient for most applications to random graphs.

Joint work with Jozsef Balogh, David Conlon, Timothy Gowers, Robert Morris, and Mathias Schacht.