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.
Back to the ACO home page