- Szemerédi regularity lemma
In
mathematics ,Szemerédi 's regularity lemma states that every large enough (finite undirected simple) graph can be "approximated" by a composition of a "structured" and a "pseudo-random" part.Formal statement of the regularity lemma
The formal statement of Szemerédi's regularity lemma requires some definitions.
Let "G" be a graph.The density of a pair of disjoint vertex sets "X", "Y" is the quantity
:d(X,Y) := frac{left| E(X,Y) ight{left|X ight|left|Y ight
where "E"("X","Y") denotes the set of edges having one end vertex in "X" and one in "Y".For ε > 0, a pair of vertex sets "X" and "Y" is called ε-pseudo-random, if for all subsets "A" of "X" and "B" of "Y" satisfying A| ge varepsilon |X| and B| ge varepsilon |Y|, we have
:left| d(X,Y) - d(A,B) ight| le varepsilon.
A partition of the vertex set of "G" into "k" sets V_1,dots,V_k is called anε-regular partition, if left| left|V_i ight| - left|V_j ight| ight| le 1 for all "i", "j", and all except varepsilon k^2 of the pairs V_i, V_j, "i" < "j", are ε-pseudo-random.
Now we are ready to state the regularity lemma.
Regularity lemma. For every ε > 0 and positive
integer "m" there exist integers "N" and "M" such that if "G" is a graph with at least "N" 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.It is a common variant in the definition of an ε-regular partition to require that the vertex sets all have the same size, while collecting the leftover vertices in an "error"-set V_0 whose size is at most an ε-fraction of the size of the vertex set of "G".
History and applications
In 1975 Szemeredi introduced a weaker version of this lemma, restricted to bipartite graphs, in order to prove what is now known as
Szemerédi's theorem . In 1976 he proved the full lemma. It has since been found to have many applications ingraph theory and computer science.References
* "Regular Partitions of Graphs," in Colloques internationaux C.N.R.S. N0. 260: Problemes Combinatoires et Theorie des graphes, p. 399. 1978. (collected from July 1976)
* 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.
Wikimedia Foundation. 2010.