In extremal graph theory, Szemerédi's regularity lemma states that a graph can be partitioned into a bounded number of parts so that the edges between parts are regular (in the sense defined below). The lemma shows that certain properties of random graphs can be applied to dense graphs like counting the copies of a given subgraph within graphs. Endre Szemerédi proved the lemma over bipartite graphs for his theorem on arithmetic progressions in 1975 and for general graphs in 1978. Variants of the lemma use different notions of regularity and apply to other mathematical objects like hypergraphs.
Statement To state Szemerédi's regularity lemma formally, we must formalize what the edge distribution between parts behaving 'almost randomly' really means. By 'almost random', we are referring to a notion called ε-regularity. To understand what this means, we first state some definitions. In what follows G is a graph with vertex set V.
Definition 1. Let X, Y be disjoint subsets of V. The edge density of the pair (X, Y) is defined as:
d ( X , Y ) := | E ( X , Y ) | | X | | Y | {\displaystyle d(X,Y):={\frac {\left|E(X,Y)\right|}{|X||Y|}}}
where E(X, Y) denotes the set of edges having one end vertex in X and one in Y.
We call a pair of parts ε-regular if, whenever you take a large subset of each part, their edge density isn't too far off the edge density of the pair of parts. Formally,
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
| d ( X , Y ) − d ( A , B ) | ≤ ε . {\displaystyle \left|d(X,Y)-d(A,B)\right|\leq \varepsilon .}
The natural way to define an ε-regular partition should be one where each pair of parts is ε-regular. However, some graphs, such as the half graphs, require many pairs of partitions (but a small fraction of all pairs) to be irregular. So we shall define ε-regular partitions to be one where most pairs of parts are ε-regular.
Definition 3. A partition of V {\displaystyle V} into k {\displaystyle k} sets P = { V 1 , … , V k } {\displaystyle {\mathcal {P}}=\{V_{1},\ldots ,V_{k}\}} is called an ε {\displaystyle \varepsilon } -regular partition if
∑ ( V i , V j ) not ε -regular | V i | | V j | ≤ ε | V ( G ) | 2 {\displaystyle \sum _{(V_{i},V_{j}){\text{ not }}\varepsilon {\text{-regular}}}|V_{i}||V_{j}|\leq \varepsilon |V(G)|^{2}}
Now we can state the lemma:
Szemerédi's 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. The bound M for the number of parts in the partition of the graph given by the proofs of Szemeredi's regularity lemma is very large, given by a O(ε−5)-level iterated exponential of m. At one time it was hoped that the true bound was much smaller, which would have had several useful applications. However Gowers (1997) found examples of graphs for which M does indeed grow very fast and is at least as large as a ε−1/16-level iterated exponential of m.
Proof
We shall find an ε-regular partition for a given graph following an algorithm:
Start with a partition While the partition isn't ε-regular: Find the subsets which witness ε-irregularity for each irregular pair. Refine the partition using all the witnessing subsets. We apply a technique called the energy increment argument to show that this process stops after a bounded number of steps. To do this, we define a measure which must increase by a certain amount in each step, but it's bounded above and thus cannot increase indefinitely. This measure is called 'energy' as it's an L 2 {\displaystyle L^{2}} quantity.
Definition 4. Let U, W be subsets of V. Set | V | = n {\displaystyle |V|=n} . The energy of the pair (U, W) is defined as:
q ( U , W ) := | U | | W | n 2 d ( U , W ) 2 {\displaystyle q(U,W):={\frac {|U||W|}{n^{2}}}d(U,W)^{2}}
For partitions P U = { U 1 , … , U k } {\displaystyle {\mathcal {P}}_{U}=\{U_{1},\ldots ,U_{k}\}} of U and P W = { W 1 , … , W l } {\displaystyle {\mathcal {P}}_{W}=\{W_{1},\ldots ,W_{l}\}} of W, we define the energy to be the sum of the energies between each pair of parts:
q ( P U , P W ) := ∑ i = 1 k ∑ j = 1 l q ( U i , W j ) {\displaystyle q({\mathcal {P}}_{U},{\mathcal {P}}_{W}):=\sum _{i=1}^{k}\sum _{j=1}^{l}q(U_{i},W_{j})}
Finally, for a partition P = { V 1 , … , V k } {\displaystyle {\mathcal {P}}=\{V_{1},\ldots ,V_{k}\}} of V, define the energy of P {\displaystyle {\mathcal {P}}} to be q ( P , P ) {\displaystyle q({\mathcal {P}},{\mathcal {P}})} . Specifically,
q ( P ) = ∑ i = 1 k ∑ j = 1 k q ( V i , V j ) = ∑ i = 1 k ∑ j = 1 k | V i | | V j | n 2 d ( V i , V j ) 2 {\displaystyle q({\mathcal {P}})=\sum _{i=1}^{k}\sum _{j=1}^{k}q(V_{i},V_{j})=\sum _{i=1}^{k}\sum _{j=1}^{k}{\frac {|V_{i}||V_{j}|}{n^{2}}}d(V_{i},V_{j})^{2}}
Note that energy is between 0 and 1 because edge density is bounded above by 1:
q ( P ) = ∑ i = 1 k ∑ j = 1 k | V i | | V j | n 2 d ( V i , V j ) 2 ≤ ∑ i = 1 k ∑ j = 1 k | V i | | V j | n 2 = 1 {\displaystyle q({\mathcal {P}})=\sum _{i=1}^{k}\sum _{j=1}^{k}{\frac {|V_{i}||V_{j}|}{n^{2}}}d(V_{i},V_{j})^{2}\leq \sum _{i=1}^{k}\sum _{j=1}^{k}{\frac {|V_{i}||V_{j}|}{n^{2}}}=1}
Now, we start by proving that energy does not decrease upon refinement.
Lemma 1. (Energy is nondecreasing under partitioning) For any partitions P U {\displaystyle {\mathcal {P}}_{U}} and P W {\displaystyle {\mathcal {P}}_{W}} of vertex sets U {\displaystyle U} and W {\displaystyle W} , q ( P U , P W ) ≥ q ( U , W ) {\displaystyle q({\mathcal {P}}_{U},{\mathcal {P}}_{W})\geq q(U,W)} .
Proof: Let P U = { U 1 , … , U k } {\displaystyle {\mathcal {P}}_{U}=\{U_{1},\ldots ,U_{k}\}} and P W = { W 1 , … , W l } {\displaystyle {\mathcal {P}}_{W}=\{W_{1},\ldots ,W_{l}\}} . Choose vertices x {\displaystyle x} uniformly from U {\displaystyle U} and y {\displaystyle y} uniformly from W {\displaystyle W} , with x {\displaystyle x} in part U i {\displaystyle U_{i}} and y {\displaystyle y} in part W j {\displaystyle W_{j}} . Then define the random variable Z = d ( U i , W j ) {\displaystyle Z=d(U_{i},W_{j})} . Let us look at properties of Z {\displaystyle Z} . The expectation is
E [ Z ] = ∑ i = 1 k ∑ j = 1 l | U i | | U | | W j | | W | d ( U i , W j ) = e ( U , W ) | U | | W | = d ( U , W ) {\displaystyle \mathbb {E} [Z]=\sum _{i=1}^{k}\sum _{j=1}^{l}{\frac {|U_{i}|}{|U|}}{\frac {|W_{j}|}{|W|}}d(U_{i},W_{j})={\frac {e(U,W)}{|U||W|}}=d(U,W)}
The second moment is
E [ Z 2 ] = ∑ i = 1 k ∑ j = 1 l | U i | | U | | W j | | W | d ( U i , W j ) 2 = n 2 | U | | W | q ( P U , P W ) {\displaystyle \mathbb {E} [Z^{2}]=\sum _{i=1}^{k}\sum _{j=1}^{l}{\frac {|U_{i}|}{|U|}}{\frac {|W_{j}|}{|W|}}d(U_{i},W_{j})^{2}={\frac {n^{2}}{|U||W|}}q({\mathcal {P}}_{U},{\mathcal {P}}_{W})}
By convexity, E [ Z 2 ] ≥ E [ Z ] 2 {\displaystyle \mathbb {E} [Z^{2}]\geq \mathbb {E} [Z]^{2}} . Rearranging, we get that q ( P U , P W ) ≥ q ( U , W ) {\displaystyle q({\mathcal {P}}_{U},{\mathcal {P}}_{W})\geq q(U,W)} for all U , W {\displaystyle U,W} . ◻ {\displaystyle \square }
If each part of P {\displaystyle {\mathcal {P}}} is further partitioned, the new partition is called a refinement of P {\displaystyle {\mathcal {P}}} . Now, if P = { V 1 , … , V m } {\displaystyle {\mathcal {P}}=\{V_{1},\ldots ,V_{m}\}} , applying Lemma 1 to each pair ( V i , V j ) {\displaystyle (V_{i},V_{j})} proves that for every refinement P ′ {\displaystyle {\mathcal {P'}}} of P {\displaystyle {\mathcal {P}}} , q ( P ′ ) ≥ q ( P ) {\displaystyle q({\mathcal {P'}})\geq q({\mathcal {P}})} . Thus the refinement step in the algorithm doesn't lose any energy.
Lemma 2. (Energy boost lemma) If ( U , W ) {\displaystyle (U,W)} is not ε {\displaystyle \varepsilon } -regular as witnessed by U 1 ⊂ U , W 1 ⊂ W {\displaystyle U_{1}\subset U,W_{1}\subset W} , then,
q ( { U 1 , U ∖ U 1 } , { W 1 , W ∖ W 1 } ) > q ( U , W ) + ε 4 | U | | W | n 2 {\displaystyle q\left(\{U_{1},U\backslash U_{1}\},\{W_{1},W\backslash W_{1}\}\right)>q(U,W)+\varepsilon ^{4}{\frac {|U||W|}{n^{2}}}}
Proof: Define Z {\displaystyle Z} as above. Then,
V a r ( Z ) = E [ Z 2 ] − E [ Z ] 2 = n 2 | U | | W | ( q ( { U 1 , U ∖ U 1 } , { W 1 , W ∖ W 1 } ) − q ( U , W ) ) {\displaystyle Var(Z)=\mathbb {E} [Z^{2}]-\mathbb {E} [Z]^{2}={\frac {n^{2}}{|U||W|}}\left(q\left(\{U_{1},U\backslash U_{1}\},\{W_{1},W\backslash W_{1}\}\right)-q(U,W)\right)}
But observe that | Z − E [ Z ] | = | d ( U 1 , W 1 ) − d ( U , W ) | {\displaystyle |Z-\mathbb {E} [Z]|=|d(U_{1},W_{1})-d(U,W)|} with probability | U 1 | | U | | W 1 | | W | {\displaystyle {\frac {|U_{1}|}{|U|}}{\frac {|W_{1}|}{|W|}}} (corresponding to x ∈ U 1 {\displaystyle x\in U_{1}} and y ∈ W 1 {\displaystyle y\in W_{1}} ), so
V a r ( Z ) = E [ ( Z − E [ Z ] ) 2 ] ≥ | U 1 | | U | | W 1 | | W | ( d ( U 1 , W 1 ) − d ( U , W ) ) 2 > ε ⋅ ε ⋅ ε 2 {\displaystyle Var(Z)=\mathbb {E} [(Z-\mathbb {E} [Z])^{2}]\geq {\frac {|U_{1}|}{|U|}}{\frac {|W_{1}|}{|W|}}(d(U_{1},W_{1})-d(U,W))^{2}>\varepsilon \cdot \varepsilon \cdot \varepsilon ^{2}} ◻ {\displaystyle \square }
Now we can prove the energy increment argument, which shows that energy increases substantially in each iteration of the algorithm.
Lemma 3 (Energy increment lemma) If a partition P = { V 1 , … , V k } {\displaystyle {\mathcal {P}}=\{V_{1},\ldots ,V_{k}\}} of V ( G ) {\displaystyle V(G)} is not ε {\displaystyle \varepsilon } -regular, then there exists a refinement Q {\displaystyle {\mathcal {Q}}} of P {\displaystyle {\mathcal {P}}} where every V i {\displaystyle V_{i}} is partitioned into at most 2 k {\displaystyle 2^{k}} parts such that
q ( Q ) ≥ q ( P ) + ε 5 . {\displaystyle q({\mathcal {Q}})\geq q({\mathcal {P}})+\varepsilon ^{5}.}
Proof: For all ( i , j ) {\displaystyle (i,j)} such that ( V i , V j ) {\displaystyle (V_{i},V_{j})} is not ε {\displaystyle \varepsilon } -regular, find A i , j ⊂ V i {\displaystyle A^{i,j}\subset V_{i}} and A j , i ⊂ V j {\displaystyle A^{j,i}\subset V_{j}} that witness irregularity (do this simultaneously for all irregular pairs). Let Q {\displaystyle {\mathcal {Q}}} be a common refinement of P {\displaystyle {\mathcal {P}}} by A i , j {\displaystyle A^{i,j}} 's. Each V i {\displaystyle V_{i}} is partitioned into at most 2 k {\displaystyle 2^{k}} parts as desired. Then,
q ( Q ) = ∑ ( i , j ) ∈ [ k ] 2 q ( Q V i , Q V j ) = ∑ ( V i , V j ) ε -regular q ( Q V i , Q V j ) + ∑ ( V i , V j ) not ε -regular q ( Q V i , Q V j ) {\displaystyle q({\mathcal {Q}})=\sum _{(i,j)\in [k]^{2}}q({\mathcal {Q}}_{V_{i}},{\mathcal {Q}}_{V_{j}})=\sum _{(V_{i},V_{j}){\text{ }}\varepsilon {\text{-regular}}}q({\mathcal {Q}}_{V_{i}},{\mathcal {Q}}_{V_{j}})+\sum _{(V_{i},V_{j}){\text{ not }}\varepsilon {\text{-regular}}}q({\mathcal {Q}}_{V_{i}},{\mathcal {Q}}_{V_{j}})}
Where Q V i {\displaystyle {\mathcal {Q}}_{V_{i}}} is the partition of V i {\displaystyle V_{i}} given by Q {\displaystyle {\mathcal {Q}}} . By Lemma 1, the above quantity is at least
∑ ( V i , V j ) ε -regular q ( V i , V j ) + ∑ ( V i , V j ) not ε -regular q ( { A i , j , V i ∖ A i , j } , { A j , i , V j ∖ A j , i } ) {\displaystyle \sum _{(V_{i},V_{j}){\text{ }}\varepsilon {\text{-regular}}}q(V_{i},V_{j})+\sum _{(V_{i},V_{j}){\text{ not }}\varepsilon {\text{-regular}}}q(\{A^{i,j},V_{i}\backslash A^{i,j}\},\{A^{j,i},V_{j}\backslash A^{j,i}\})}
Since V i {\displaystyle V_{i}} is cut by A i , j {\displaystyle A^{i,j}} when creating Q {\displaystyle {\mathcal {Q}}} , so Q V i