Szemerédi regularity lemma

In mathematics, the Szemerédi regularity lemma states that every large enough graph can be divided into subsets of about the same size so that the edges between different subsets behave almost randomly. Szemerédi (1975) introduced a weaker version of this lemma, restricted to bipartite graphs, in order to prove Szemerédi's theorem, and in (Szemerédi 1978) he proved the full lemma. Extensions of the regularity method to hypergraphs were obtained by Rödl and his collaborators and Gowers.

The formal statement of Szemerédi's regularity lemma requires some definitions. In what follows G is a graph with vertex set V.

Definition 1. Let X, Y be disjoint subsets of V. The density of the pair (X, Y) is defined as:

Definition 2. For ε > 0, a pair of vertex sets X and Y is called ε-regular, if for all subsets A ⊆ X, B ⊆ Y satisfying |A| ≥ ε|X|, |B| ≥ ε|Y|, we have

Definition 3. A partition of V into k sets: V₁, ...,  V_k, is called an ε-regular partition, if:

Now we can state the lemma:

Regularity Lemma. For every ε > 0 and positive integer m there exists an integer M such that if G is a graph with at least m vertices, there exists an integer k in the range m ≤ k ≤ M and an ε-regular partition of the vertex set of G into k sets whose sizes differ by at most 1.

...
Wikipedia