Szemerédi regularity lemma

From Wikipedia, the free encyclopedia

Jump to: navigation, search

In mathematics, Szemerédi's regularity lemma states that every large enough graph can be divided into subsets of about the same size so that the edges between different subsets behave almost randomly. Szemerédi (1975) introduced a weaker version of this lemma, restricted to bipartite graphs, in order to prove Szemerédi's theorem, and in (Szemerédi 1978) he proved the full lemma. There are several extension of the regularity lemma to hypergraphs, such as Tao (2006).

[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.

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\right| - \left|V_j\right| \right| \le 1 for all i, j, and all except \varepsilon k^2 of the pairs Vi, Vj, 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 an integer M such that if G is a graph with at least m edges, 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 V0 whose size is at most an ε-fraction of the size of the vertex set of G.

The bound M for the number of parts in the partition of the graph given by the proofs of Szemeredi's regularity lemma is very large, given by a log(1/ε5)-level iterated exponential of m. At one time it was hoped that the true bound was much smaller, which would have had several useful applications. However Gowers (1997) found examples of graphs for which M does indeed grow very fast and is at least as large as a log(1/ε)-level iterated exponential of m. In particular the best bound has level exactly 4 in the Grzegorczyk hierarchy, and so is not an elementary recursive function.

[edit] Extensions

Komlós, Sárközy and Szemerédi later proved in the blow-up lemma that the regular pairs in Szemerédi regularity lemma behave like complete bipartite graphs under the correct conditions. The lemma allowed for deeper exploration into the nature of embeddings of large sparse graphs into dense graphs.

[edit] References

Retrieved from "http://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemma"
Languages