User:TomSSmith/SzemeredisLemma

From Wikipedia, the free encyclopedia

Szemerédi's regularity lemma is a technical result in graph theory which turns out to have a remarkable number of applications. Very roughly speaking, the lemma says that any graph can be broken into a finite number of pieces in such that most pairs of pieces behave regularly, ie like a randomly-generated bipartite graph. Moreover, the number of pieces is bounded only by what proportion of irregular pairs we are prepared to allow.

[edit] Statement of the lemma

There are several terms that must be defined in order to state Szemerédi's regularity lemma:

A partition of a set is equitable if every class in the partition except for one exceptional class contains the same number of elements.

In mathematics, Szemerédi's regularity lemma states that for every ε > 0 and every positive integer t there is an integer

such that every graph with n > t vertices has an ε-regular partition into k + 1 classes, t ≤ k ≤ T.

This lemma was introduced by Szemerédi in 1975 in order to prove what is now known as Szemerédi's theorem. It has since been found to have many applications in graph theory and computer science.

[edit] References

• Komlós, János; Miklos Simonovits: Szemerédi's regularity lemma and its applications in graph theory. Combinatorics, Paul Erdös is eighty, Vol. 2 (Keszthely, 1993), 295-352, Bolyai Soc. Math. Stud., 2, János Bolyai Math. Soc., Budapest, 1996.
• Komlós, János; Ali Shokoufandeh; Miklós Simonovits; Endre Szemerédi: The regularity lemma and its applications in graph theory. Theoretical aspects of computer science (Tehran, 2000), 84-112, Lecture Notes in Comput. Sci., 2292, Springer, Berlin, 2002.