Szemerédi regularity lemma

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. 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.

Applications[edit]

Graph counting lemma[edit]

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.

${\mathcal {Q}}$ refines ${\mathcal {P}}$ , that is every part of ${\mathcal {P}}$ is the union of some collection of parts in ${\mathcal {Q}}$ .

${\mathcal {P}}$ is $\epsilon _{0}$ -regular and ${\mathcal {Q}}$ is $\epsilon _{|{\mathcal {P}}|}$ -regular.

$q({\mathcal {Q}})<q({\mathcal {P}})+\epsilon _{0}$

$|{\mathcal {Q}}|\leq M$

; 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., vol. 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, vol. 2292, Springer, Berlin, pp. 84–112, doi:10.1007/3-540-45878-6_3, ISBN 978-3-540-43328-6, MR 1966181.

Komlós, J.

Edmonds, Chelsea; Koutsoukou-Argyraki, Angeliki; Szemerédi's regularity lemma (Formal proof development in Isabelle/HOL, Archive of Formal Proofs)

Szemerédi regularity lemma

Applications[edit]

Graph counting lemma[edit]

Komlós, J.

Komlós, J.

Paulson, Lawrence C.