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&epsilon;-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 &epsilon;-pseudo-random.

Now we are ready to state the regularity lemma.

Regularity lemma. For every &epsilon; > 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" &le; "k" &le;"M" and an &epsilon;-regular partition of the vertex set of "G" into "k" sets.

It is a common variant in the definition of an &epsilon;-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 &epsilon;-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 in graph 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.