Abstract

Szemerédi’s regularity lemma is a fundamental tool in extremal combinatorics. However, the original version is only helpful in studying dense graphs. In the 1990s, Kohayakawa and Rödl proved an analogue of Szemerédi’s regularity lemma for sparse graphs as part of a general program toward extending extremal results to sparse graphs. Many of the key applications of Szemerédi’s regularity lemma use an associated counting lemma. In order to prove extensions of these results which also apply to sparse graphs, it remained a well-known open problem to prove a counting lemma in sparse graphs.

In this talk, we discuss two different counting lemmas, each of which complements the sparse regularity lemma of Kohayakawa and R\”odl, but in different contexts. The first, which is joint work with Gowers, Samotij and Schacht, deals with the case when the sparse graph is a subgraph of a random graph, while the second, which is joint work with Fox and Zhao, deals with the case when the sparse graph is a subgraph of a pseudorandom graph. We use these results to prove sparse extensions of several well-known combinatorial theorems, including the removal lemmas for graphs and groups, the Erdős-Stone-Simonovits theorem and Ramsey’s theorem. In particular, we show how these methods can be used to give a substantially simpler proof of the Green-Tao theorem about primes in arithmetic progression.