Szemerédi regularity lemma

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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,[1] and in (Szemerédi 1978) he proved the full lemma.[2] Extensions of the regularity method to hypergraphs were obtained by Rödl and his collaborators[3][4][5] and Gowers.[6][7]

Statement[edit]

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 XY be disjoint subsets of V. The density of the pair (XY) is defined as:

where E(XY) denotes the set of edges having one end vertex in X and one in Y.

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: V1, ...,  Vk, is called an ε-regular partition, if:

  • for all ij we have: ||Vi| − |Vj|| ≤ 1;
  • all except εk2 of the pairs Vi, Vj, i < j, are ε-regular.

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.

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. In particular the best bound has level exactly 4 in the Grzegorczyk hierarchy, and so is not an elementary recursive function.[8]

Extensions[edit]

János Komlós, Gábor Sárközy and Endre Szemerédi later (in 1997) proved in the blow-up lemma[9][10] 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.

An inequality of Terence Tao extends the Szemerédi regularity lemma.[11]

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.[12]

See also[edit]

References[edit]

  1. ^ 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 .
  2. ^ 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 .
  3. ^ 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 .
  4. ^ 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 .
  5. ^ Nagle, Brendan; Rödl, Vojtěch; Schacht, Mathias (2006), "The counting lemma for regular k-uniform hypergraphs", Random Structures & Algorithms, 28 (2): 113–179, doi:10.1002/rsa.20117, MR 2198495 .
  6. ^ 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 .
  7. ^ Gowers, W. T. (2007), "Hypergraph regularity and the multidimensional Szemerédi theorem", Annals of Mathematics, Second Series, 166 (3): 897–946, doi:10.4007/annals.2007.166.897, MR 2373376 .
  8. ^ 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 .
  9. ^ 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 
  10. ^ 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, doi:10.1002/(SICI)1098-2418(199805)12:3<297::AID-RSA5>3.3.CO;2-W, MR 1635264 
  11. ^ Tao, Terence (2006), "Szemerédi's regularity lemma revisited", Contributions to Discrete Mathematics, 1 (1): 8–28, arXiv:math/0504472Freely accessible, MR 2212136 .
  12. ^ Conlon, David; Fox, Jacob (2012), "Bounds for graph regularity and removal lemmas", Geometric and Functional Analysis, 22 (5): 1191–1256, arXiv:1107.4829Freely accessible, doi:10.1007/s00039-012-0171-x, MR 2989432 

Additional reading[edit]