In the previous two chapters, we have encountered two main types of “extremal” constructions of graphs which minimize or maximize the number of copies of a given graph, under certain constraints:
Partition the vertex set into a bounded number of “parts.” Join two vertices with an edge if they are in different parts, but not if they are in the same part. (Mantel’s Theorem, Turán’s Theorem, the Erdős–Stone Theorem)
The focus of this chapter is on the remarkable fact that the structure of any graph \(G\) can be described as a mixture of these two types of constructions, up to small errors; this is known as the Szemerédi Regularity Lemma [278]. Note that, unlike in previous chapters, we are speaking about any graph here, with no assumptions on it being an extremal configuration for any particular combinatorial problem. Therefore, the Regularity Lemma is more than just a useful tool for extremal combinatorics; it is a profound statement about the nature of graphs themselves.
