Szemerédi regularity lemma

Szemerédi's regularity lemma is one of the most powerful tools in extremal graph theory, particularly in the study of large dense graphs. It states that the vertices of every large enough graph can be partitioned into a bounded number of parts so that the edges between different parts behave almost randomly.

The edges between parts behave in a "random-like" fashion.

According to the lemma, no matter how large a graph is, we can approximate it with the edge densities between a bounded number of parts. Between any two parts, the distribution of edges will be pseudorandom as per the edge density. These approximations provide essentially correct values for various properties of the graph, such as the number of embedded copies of a given subgraph or the number of edge deletions required to remove all copies of some subgraph.

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're 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:

${\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.

Subset pairs of a regular pair are similar in edge density to the original pair.

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

${\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.[1] So we shall define ε-regular partitions to be one where most pairs of parts are ε-regular.

Definition 3. A partition of ${\displaystyle V}$ into ${\displaystyle k}$ sets ${\displaystyle {\mathcal {P}}=\{V_{1},\ldots ,V_{k}\}}$ is called an ${\displaystyle \varepsilon }$-regular partition if

${\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(ε⁻⁵)-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. In particular the best bound has level exactly 4 in the Grzegorczyk hierarchy, and so is not an elementary recursive function.[2]

Proof

The boundaries of irregularity witnessing subsets refine each part of the partition.

We shall find an ε-regular partition for a given graph following an algorithm. A rough outline:

1. Start with an arbitrary partition (could just be 1 part)
2. While the partition isn't ε-regular:
   • Find the subsets which witness ε-irregularity for each irregular pair.
   • Simultaneously refine the partition using all the witnessing subsets.

We apply a technique called the energy increment argument to show that this process terminates after a bounded number of steps. Basically, we define a monovariant which must increase by a certain amount in each step, but it's bounded above and thus cannot increase indefinitely. This monovariant is called 'energy' as it's an ${\displaystyle L^{2}}$ quantity.

Definition 4. Let U, W be subsets of V. Set ${\displaystyle |V|=n}$. The energy of the pair (U, W) is defined as:

${\displaystyle q(U,W):={\frac {|U||W|}{n^{2}}}d(U,W)^{2}}$

For partitions ${\displaystyle {\mathcal {P}}_{U}=\{U_{1},\ldots ,U_{k}\}}$ of U and ${\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:

${\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 ${\displaystyle {\mathcal {P}}=\{V_{1},\ldots ,V_{k}\}}$ of V, define the energy of ${\displaystyle {\mathcal {P}}}$ to be ${\displaystyle q({\mathcal {P}},{\mathcal {P}})}$. Specifically,

${\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}}$

Observe that energy is between 0 and 1 because edge density is bounded above by 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 ${\displaystyle {\mathcal {P}}_{U}}$ and ${\displaystyle {\mathcal {P}}_{W}}$ of vertex sets ${\displaystyle U}$ and ${\displaystyle W}$, ${\displaystyle q({\mathcal {P}}_{U},{\mathcal {P}}_{W})\geq q(U,W)}$.

Proof: Let ${\displaystyle {\mathcal {P}}_{U}=\{U_{1},\ldots ,U_{k}\}}$ and ${\displaystyle {\mathcal {P}}_{W}=\{W_{1},\ldots ,W_{l}\}}$. Choose vertices ${\displaystyle x}$ uniformly from ${\displaystyle U}$ and ${\displaystyle y}$ uniformly from ${\displaystyle W}$, with ${\displaystyle x}$ in part ${\displaystyle U_{i}}$ and ${\displaystyle y}$ in part ${\displaystyle W_{j}}$. Then define the random variable ${\displaystyle Z=d(U_{i},W_{j})}$. Let us look at properties of ${\displaystyle Z}$. The expectation is

${\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

${\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, ${\displaystyle \mathbb {E} [Z^{2}]\geq \mathbb {E} [Z]^{2}}$. Rearranging, we get that ${\displaystyle q({\mathcal {P}}_{U},{\mathcal {P}}_{W})\geq q(U,W)}$ for all ${\displaystyle U,W}$.${\displaystyle \square }$

If each part of ${\displaystyle {\mathcal {P}}}$ is further partitioned, the new partition is called a refinement of ${\displaystyle {\mathcal {P}}}$. Now, if ${\displaystyle {\mathcal {P}}=\{V_{1},\ldots ,V_{m}\}}$, applying Lemma 1 to each pair ${\displaystyle (V_{i},V_{j})}$ proves that for every refinement ${\displaystyle {\mathcal {P'}}}$ of ${\displaystyle {\mathcal {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 ${\displaystyle (U,W)}$ is not ${\displaystyle \varepsilon }$-regular as witnessed by ${\displaystyle U_{1}\subset U,W_{1}\subset W}$, then,

${\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 ${\displaystyle Z}$ as above. Then,

${\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 ${\displaystyle |Z-\mathbb {E} [Z]|=|d(U_{1},W_{1})-d(U,W)|}$ with probability ${\displaystyle {\frac {|U_{1}|}{|U|}}{\frac {|W_{1}|}{|W|}}}$(corresponding to ${\displaystyle x\in U_{1}}$ and ${\displaystyle y\in W_{1}}$), so

${\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 ${\displaystyle {\mathcal {P}}=\{V_{1},\ldots ,V_{k}\}}$ of ${\displaystyle V(G)}$ is not ${\displaystyle \varepsilon }$-regular, then there exists a refinement ${\displaystyle {\mathcal {Q}}}$ of ${\displaystyle {\mathcal {P}}}$ where every ${\displaystyle V_{i}}$ is partitioned into at most ${\displaystyle 2^{k}}$ parts such that

${\displaystyle q({\mathcal {Q}})\geq q({\mathcal {P}})+\varepsilon ^{5}.}$

Proof: For all ${\displaystyle (i,j)}$ such that ${\displaystyle (V_{i},V_{j})}$ is not ${\displaystyle \varepsilon }$-regular, find ${\displaystyle A^{i,j}\subset V_{i}}$ and ${\displaystyle A^{j,i}\subset V_{j}}$ that witness irregularity (do this simultaneously for all irregular pairs). Let ${\displaystyle {\mathcal {Q}}}$ be a common refinement of ${\displaystyle {\mathcal {P}}}$ by ${\displaystyle A^{i,j}}$'s. Each ${\displaystyle V_{i}}$ is partitioned into at most ${\displaystyle 2^{k}}$ parts as desired. Then,

${\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 ${\displaystyle {\mathcal {Q}}_{V_{i}}}$ is the partition of ${\displaystyle V_{i}}$ given by ${\displaystyle {\mathcal {Q}}}$. By Lemma 1, the above quantity is at least

${\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 ${\displaystyle V_{i}}$ is cut by ${\displaystyle A^{i,j}}$ when creating ${\displaystyle {\mathcal {Q}}}$, so ${\displaystyle {\mathcal {Q}}_{V_{i}}}$ is a refinement of ${\displaystyle \{A^{i,j},V_{i}\backslash A^{i,j}\}}$. By lemma 2, the above sum is at least

${\displaystyle \sum _{(i,j)\in [k]^{2}}q(V_{i},V_{j})+\sum _{(V_{i},V_{j}){\text{ not }}\varepsilon {\text{-regular}}}\varepsilon ^{4}{\frac {|V_{i}||V_{j}|}{n^{2}}}}$

But the second sum is at least ${\displaystyle \varepsilon ^{5}}$ since ${\displaystyle {\mathcal {P}}}$ is not ${\displaystyle \varepsilon }$-regular, so we deduce the desired inequality. ${\displaystyle \square }$

Now, starting from any partition, we can keep applying Lemma 3 as long as the resulting partition isn't ${\displaystyle \varepsilon }$-regular. But in each step energy increases by ${\displaystyle \varepsilon ^{5}}$, and it's bounded above by 1. Then this process can be repeated at most ${\displaystyle \varepsilon ^{-5}}$ times, before it terminates and we must have an ${\displaystyle \varepsilon }$-regular partition.

Applications

If we have enough information about the regularity of a graph, we can count the number of copies of a specific subgraph within the graph up to small error.

Graph Counting Lemma. Let ${\displaystyle H}$ be a graph with ${\displaystyle V(H)=[k]}$, and let ${\displaystyle \varepsilon >0}$. Let ${\displaystyle G}$ be an ${\displaystyle n}$-vertex graph with vertex sets ${\displaystyle V_{1},\dots ,V_{k}\subseteq V(G)}$ such that ${\displaystyle (V_{i},V_{j})}$ is ${\displaystyle \varepsilon }$-regular whenever ${\displaystyle \{i,j\}\in E(H)}$. Then, the number of labeled copies of ${\displaystyle H}$ in ${\displaystyle G}$ is within ${\displaystyle e(H)\varepsilon |V_{1}|\cdots |V_{k}|}$ of

${\displaystyle \left(\prod _{\{i,j\}\in E(H)}d(V_{i},V_{j})\right)\left(\prod _{i=1}^{k}|V_{i}|\right)}$

This can be combined with Szemerédi's regularity lemma to prove the Graph removal lemma. The graph removal lemma can be used to prove Roth's Theorem on Arithmetic Progressions,[3] and a generalization of it, the hypergraph removal lemma, can be used to prove Szemerédi's theorem.[4]

The graph removal lemma generalizes to induced subgraphs, by considering edge edits instead of only edge deletions. This was proved by Alon, Fischer, Krivelevich, and Szegedy in 2000.[5] However, this required a stronger variation of the regularity lemma.

Szemerédi's regularity lemma does not provide meaningful results in sparse graphs. Since sparse graphs have subconstant edge densities, ${\displaystyle \varepsilon }$-regularity is trivially satisfied. Even though the result seems purely theoretical, some attempts [6][7] have been made to use the regularity method as compression technique for large graphs.

History and Extensions

Gowers's construction for the lower bound of Szemerédi's regularity lemma

Szemerédi (1975) first introduced a weaker version of this lemma, restricted to bipartite graphs, in order to prove Szemerédi's theorem,[8] and in (Szemerédi 1978) he proved the full lemma.[9] Extensions of the regularity method to hypergraphs were obtained by Rödl and his collaborators[10][11][12] and Gowers.[13][14]

János Komlós, Gábor Sárközy and Endre Szemerédi later (in 1997) proved in the blow-up lemma[15][16] that the regular pairs in Szemerédi regularity lemma behave like complete bipartite graphs under the correct conditions. The lemma allowed for deeper exploration into the nature of embeddings of large sparse graphs into dense graphs.

The first constructive version was provided by Alon, Duke, Lefmann, Rödl and Yuster.[17] Subsequently, Frieze and Kannan gave a different version and extended it to hypergraphs.[18] They later produced a different construction due to Alan Frieze and Ravi Kannan that uses singular values of matrices.[19] One can find more efficient non-deterministic algorithms, as formally detailed in Terence Tao's blog[20] and implicitly mentioned in various papers.[21][22][23]

An inequality of Terence Tao extends the Szemerédi regularity lemma, by revisiting it from the perspective of probability theory and information theory instead of graph theory.[24] Terence Tao has also provided a proof of the lemma based on spectral theory, using the adjacency matrices of graphs.[25]

It is not possible to prove a variant of the regularity lemma in which all pairs of partition sets are regular. Some graphs, such as the half graphs, require many pairs of partitions (but a small fraction of all pairs) to be irregular.[26]

It is a common variant in the definition of an ${\displaystyle \varepsilon }$-regular partition to require that the vertex sets all have the same size, while collecting the leftover vertices in an "error"-set ${\displaystyle V_{0}}$ whose size is at most an ${\displaystyle \varepsilon }$-fraction of the size of the vertex set of ${\displaystyle G}$.

A stronger variation of the regularity lemma was proven by Alon, Fischer, Krivelevich, and Szegedy while proving the induced graph removal lemma. This works with a sequence of ${\displaystyle \varepsilon }$ instead of just one, and shows that there exists a partition with an extremely regular refinement, where the refinement doesn't have too large of an energy increment.

Szemerédi's regularity lemma can be interpreted as saying that the space of all graphs is totally bounded (and hence precompact) in a suitable metric (the cut distance). Limits in this metric can be represented by graphons; another version of the regularity lemma simply states that the space of graphons is compact.[27]

References

1. Conlon, David; Fox, Jacob (2012), "Bounds for graph regularity and removal lemmas", Geometric and Functional Analysis, 22 (5): 1191–1256, arXiv:1107.4829, doi:10.1007/s00039-012-0171-x, MR 2989432
2. Gowers, W. T. (1997), "Lower bounds of tower type for Szemerédi's uniformity lemma", Geometric and Functional Analysis, 7 (2): 322–337, doi:10.1007/PL00001621, MR 1445389.
3. Roth, K. F. (1953), "On certain sets of integers", Journal of the London Mathematical Society, 28 (1): 104–109, doi:10.1112/jlms/s1-28.1.104, MR 0051853
4. Tao, Terence (2006), "A variant of the hypergraph removal lemma", Journal of Combinatorial Theory, Series A, 113 (7): 1257–1280, arXiv:math/0503572, doi:10.1016/j.jcta.2005.11.006, MR 2259060
5. Alon, Noga; Fischer, Eldar; Krivelevich, Michael; Szegedy, Mario (2000), "Efficient testing of large graphs", Combinatorica, 20 (4): 451–476, doi:10.1007/s004930070001, MR 1804820
6. Pelosin, Francesco (2018). "Graph Compression Using The Regularity Method". Cite journal requires |journal= (help)
7. Fiorucci, Marco; Pelosin, Francesco; Pelillo, Marcello (2020). "Separating structure from noise in large graphs using the regularity lemma". Volume 98. Cite journal requires |journal= (help)
8. Szemerédi, Endre (1975), "On sets of integers containing no k elements in arithmetic progression", Polska Akademia Nauk. Instytut Matematyczny. Acta Arithmetica, 27: 199–245, MR 0369312.
9. Szemerédi, Endre (1978), "Regular partitions of graphs", Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), Colloq. Internat. CNRS, 260, Paris: CNRS, pp. 399–401, MR 0540024.
10. Frankl, Peter; Rödl, Vojtěch (2002), "Extremal problems on set systems", Random Structures & Algorithms, 20 (2): 131–164, doi:10.1002/rsa.10017.abs, MR 1884430.
11. Rödl, Vojtěch; Skokan, Jozef (2004), "Regularity lemma for k-uniform hypergraphs", Random Structures & Algorithms, 25 (1): 1–42, doi:10.1002/rsa.20017, MR 2069663.
12. Nagle, Brendan; Rödl, Vojtěch; Schacht, Mathias (2006), "The counting lemma for regular k-uniform hypergraphs", Random Structures & Algorithms, 28 (2): 113–179, CiteSeerX 10.1.1.378.8503, doi:10.1002/rsa.20117, MR 2198495.
13. Gowers, W. T. (2006), "Quasirandomness, counting and regularity for 3-uniform hypergraphs", Combinatorics, Probability and Computing, 15 (1–2): 143–184, doi:10.1017/S0963548305007236, MR 2195580.
14. Gowers, W. T. (2007), "Hypergraph regularity and the multidimensional Szemerédi theorem", Annals of Mathematics, Second Series, 166 (3): 897–946, arXiv:0710.3032, Bibcode:2007arXiv0710.3032G, doi:10.4007/annals.2007.166.897, MR 2373376.
15. Komlós, János; Sárközy, Gábor N.; Szemerédi, Endre (1997), "Blow-up lemma", Combinatorica, 17 (1): 109–123, doi:10.1007/BF01196135, MR 1466579
16. Komlós, János; Sárközy, Gábor N.; Szemerédi, Endre (1998), "An algorithmic version of the blow-up lemma", Random Structures & Algorithms, 12 (3): 297–312, arXiv:math/9612213, doi:10.1002/(SICI)1098-2418(199805)12:3<297::AID-RSA5>3.3.CO;2-W, MR 1635264
17. N. Alon and R. A. Duke and H. Lefmann and V. Rödl and R. Yuster (1994). "The Algorithmic Aspects of the Regularity Lemma". J. Algorithms. 16: 80–109. CiteSeerX 10.1.1.102.681. doi:10.1006/jagm.1994.1005.
18. A. Frieze and R. Kannan (1996). "The regularity lemma and approximation schemes for dense problems". FOCS '96: Proceedings of the 37th Annual Symposium on Foundations of Computer Science. doi:10.1109/SFCS.1996.548459.
19. A. Frieze and R. Kannan (1999). "A Simple Algorithm for Constructing Szemerédi's Regularity Partition" (PDF). Electron. J. Comb. 6.
20. Tao, Terence (2009), Szemeredi's regularity lemma via random partitions
21. Alon, Noga; Shapira, Asaf (2008), "Every monotone graph property is testable", SIAM J. Comput., 38 (2): 505–522, doi:10.1137/050633445, ISSN 0097-5397, MR 2411033
22. Ishigami, Yoshiyasu (2006), A Simple Regularization of Hypergraphs, arXiv:math/0612838, Bibcode:2006math.....12838I
23. Austin, Tim (2008), "On exchangeable random variables and the statistics of large graphs and hypergraphs", Probability Surveys, 5: 80–145, arXiv:0801.1698, Bibcode:2008arXiv0801.1698A, doi:10.1214/08-PS124
24. Tao, Terence (2006), "Szemerédi's regularity lemma revisited", Contributions to Discrete Mathematics, 1 (1): 8–28, arXiv:math/0504472, Bibcode:2005math......4472T, MR 2212136.
25. Tao, Terence (2012), The spectral proof of the Szemeredi regularity lemma
26. Conlon, David; Fox, Jacob (2012), "Bounds for graph regularity and removal lemmas", Geometric and Functional Analysis, 22 (5): 1191–1256, arXiv:1107.4829, doi:10.1007/s00039-012-0171-x, MR 2989432
27. Lovász, László; Szegedy, Balázs (2007), "Szemerédi's lemma for the analyst", Geometric and Functional Analysis, 17: 252–270, doi:10.1007/s00039-007-0599-6, ISSN 1016-443X, MR 2306658

Further reading

• Komlós, J.; Simonovits, M. (1996), "Szemerédi's regularity lemma and its applications in graph theory", Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), Bolyai Soc. Math. Stud., 2, János Bolyai Math. Soc., Budapest, pp. 295–352, MR 1395865.
• Komlós, J.; Shokoufandeh, Ali; Simonovits, Miklós; Szemerédi, Endre (2002), "The regularity lemma and its applications in graph theory", Theoretical aspects of computer science (Tehran, 2000), Lecture Notes in Computer Science, 2292, Springer, Berlin, pp. 84–112, doi:10.1007/3-540-45878-6_3, ISBN 978-3-540-43328-6, MR 1966181.