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.
Contents
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 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 A⊆X and B⊆Y 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
Now we are ready to state the regularity lemma.
Regularity lemma. For every
It is a common variant in the definition of an
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. Subsequently Frieze and Kannan gave a different version and extended it to hypergraphs. The paper 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
The algorithm is based on two crucial lemmas:
Lemma 1:
Fix k and
Lemma 2:
Let
(a) If there exist
(b) If
These two lemmas are combined in the following algorithmic construction of the Szemerédi regularity lemma.
[Step 1] Arbitrarily divide the vertices of
[Step 2] For every pair
[Step 3] If there are at most
[Step 4] Apply Lemma 1 where
[Step 5] Let
The algorithm will terminate with an