TOPICS
Search

Szemerédi's Regularity Lemma


A fundamental structural result in extremal graph theory due to Szemerédi (1978). The regularity lemma essentially says that every graph can be well-approximated by the union of a constant number of random-like bipartite graphs, called regular pairs.


See also

Blow-Up Lemma, Extremal Graph Theory, Seymour Conjecture, Szemerédi's Theorem

Explore with Wolfram|Alpha

References

Komlós, J. and Simonovitas, M. "Szemerédi Regularity Lemma and Its Applications in Graph Theory." In Combinatorics, Paul Erdős is Eighty, Vol. 1 (Ed. D. Miklós, V. T. Sós, and T. Szőnyi). Budapest: János Bolyai Mathematical Society, pp. 295-352, 1993.Komlós, J.; Sárkőzy, G. N.; and Szemerédi, E. "Proof of the Seymour Conjecture for Large Graphs." Ann. Comb. 2, 43-60, 1998.Szemerédi, E. "Regular Partitions of Graphs." In Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976). Paris: Éditions du Centre National de la Recherche Scientifique (CNRS), pp. 399-401, 1978.

Referenced on Wolfram|Alpha

Szemerédi's Regularity Lemma

Cite this as:

Weisstein, Eric W. "Szemerédi's Regularity Lemma." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SzemeredisRegularityLemma.html

Subject classifications