The sparse regularity method

Szemerédi's regularity lemma is a fundamental tool in extremal combinatorics, with also applications to algorithms. Roughly speaking, it says that every large dense graph can be partitioned into a bounded number of parts so that the induced bipartite graph between most pairs of parts are random-like. 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 analogues of these results for sparse graphs, it remained a well-known open problem to prove a counting lemma in sparse graphs.

In a joint work with David Conlon and Jacob Fox, we prove a counting lemma which complements the sparse regularity lemma, allowing us to extend the regularity method to subgraphs of sparse pseudorandom graphs. This allows us to extend many classical extremal combinatorial results to the sparse pseudorandom setting.