Szemerédi regularity lemma

From Wikipedia, the free encyclopedia

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.

[edit] 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) \right|}{\left|X\right|\left|Y\right|}$

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) \right| \le \varepsilon.$

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.

[edit] History and applications

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.