For sparse graphs (i.e. those with o(n^2) edges) the regularity lemma is not true in its full generality. It does hold, however, under some addition assumptions. These assumptions are satisfied for example in random graphs.
The sparse regularity lemma can thus be used to prove structural results about random graphs. We again explain some prominent examples.
Back to Combinatorics Tutorials