Mar 28, 3:30pm, Wean 8220

Wojciech Samotij, Tel Aviv University

The Kohayakawa-Luczak-Rodl conjecture

Wojciech Samotij, Tel Aviv University

The Kohayakawa-Luczak-Rodl conjecture

Abstract:

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.