Algorithmic version for Szemerédi regularity partition

From Wikipedia, the free encyclopedia
Jump to: navigation, search

A Simple Algorithm for Constructing Szemerédi's Regularity Partition is a paper by Alan M. Frieze and Ravi Kannan giving an algorithmic version of the Szemerédi regularity lemma to find an ε-regular partition of a given graph.

Formal statement of the regularity lemma[edit]

The formal statement of Szemerédi's regularity lemma requires some definitions. Let G be a graph. The density d(X,Y) of a pair of disjoint vertex sets X, Y is defined as d(X,Y)=|E(X,Y)|/|X||Y| 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 ε-regular, if for all subsets AX and BY satisfying |A| ≥ε |X| and |B| ≥ ε |Y|, we have |d(X,Y)-d(A,B)| ≤ ε.

A partition of the vertex set of G into k sets, V1,...,Vk, is called an equitable partition if for all i, j, ||Vi|-|Vj||≤1. An equitable partition is an \epsilon-regular partition, if for all but at most \epsilon{k^2} pairs (i,j) the pair (V_i, V_j,) is \epsilon-regular.

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

Szemerédi's regularity lemma is one of the most powerful tools of extremal graph theory. It says that, in some sense, all graphs can be approximated by random-looking graphs. Therefore the lemma helps in proving theorems for arbitrary graphs whenever the corresponding result is easy for random graphs. The first constructive version was provided by Alon, Duke, Leffman, Rödl and Yuster.[1] Subsequently Frieze and Kannan gave a different version and extended it to hypergraphs.[2] The paper [3] is a nice survey on regularity lemma and its various applications. Here we will briefly describe a different construction due to Alan Frieze and Ravi Kannan that uses singular values of matrices.

Constructive version of Szemerédi regularity lemma by Frieze and Kannan[edit]

The algorithm[4] is based on two crucial lemmas:

Lemma 1:
Fix k and \gamma and let G=(V,E) be a graph with n vertices. Let P be an equitable partition of V in classes V_0, V_1, ... ,V_k. Assume |V_1| > 4^{2k} and 4^k >600 \gamma ^2. Given proofs that more than \gamma k^2 pairs (V_r,V_s) are not \gamma-regular, it is possible to find in O(n) time an equitable partition P' (which is a refinement of P) into 1+k4^k classes, with an exceptional class of cardinality at most |V_0|+n/4^k and such that ind(P')ind(P) + \gamma^5/20

Lemma 2:
Let W be a R×C matrix with |R|=p, |C|=q and \|W\|_\inf\leq1 and \gamma be a positive real.
(a) If there exist SR, TC such that |S|\gamma p, |T|\gamma q and |W(S,T)|\gamma |S||T| then \sigma_1(W)\geq\gamma^3\sqrt{pq}
(b) If \sigma_1(W)\geq\gamma\sqrt{pq}, then there exist SR, TC such that |S|\gamma'p, |T|\gamma'q and W(S,T)\gamma'|S||T| where \gamma'=\gamma^3/108. Furthermore S, T can be constructed in polynomial time.

These two lemmas are combined in the following algorithmic construction of the Szemerédi regularity lemma.

[Step 1] Arbitrarily divide the vertices of G into an equitable partition P_1 with classes V_0,V_1,...,V_b where |V_i|=\lfloor n/b\rfloor and hence |V_0|<b. denote k_1=b.
[Step 2] For every pair (V_r,V_s) of P_i, compute \sigma_1(W_{r,s}). If the pair (V_r,V_s) are not \epsilon-regular then by Lemma 2 we obtain a proof that they are not \gamma=\epsilon^9/108-regular.
[Step 3] If there are at most \epsilon{k_1\choose 2} pairs that produce proofs of non \gamma-regularity that halt. P_i is \epsilon-regular.
[Step 4] Apply Lemma 1 where P=P_i, k=k_i, \gamma=\epsilon^9/108 and obtain P' with 1+k_i4^{k_i} classes
[Step 5] Let k_i+1 = k_i4^{k_i}, P_i+1=P', i=i+1 and go to Step 2.

The algorithm will terminate with an \epsilon-regular partition in O(\epsilon^{-45}) steps since the improvement at each step is \gamma^5/20=O(\epsilon^{45}).

References[edit]

  1. ^ N. Alon and R. A. Duke and H. Lefmann and V. Rödl and R. Yuster, (1994). "The Algorithmic Aspects of the Regularity Lemma". J. Algorithms. CiteSeerX: 10.1.1.102.681. 
  2. ^ A. Frieze and R. Kannan, (1996). "The regularity lemma and approximation schemes for dense problems,". FOCS '96: Proceedings of the 37th Annual Symposium on Foundations of Computer Science,. 
  3. ^ Komlós, János; Simonovits, Miklós (1996). Szemeredi's Regularity Lemma and its applications in graph theory. Technical Report: 96-10, DIMACS. .
  4. ^ A. Frieze and R. Kannan (1999). "A Simple Algorithm for Constructing Szemerédi's Regularity Partition". Electr. J. Comb. 6.