A simple algorithm for constructing Szemerédi’s Regularity Partition

Alan Frieze Department of Mathematical Sciences, Carnegie Mellon University.

                 alan@random.math.cmu.edu∗

Ravi Kannan Department of Computer Science, Yale University.

                    kannan@cs.yale.edu†

Submitted: November 25, 1998; Accepted: March 15, 1999.

Abstract

We give a simple constructive version of Szemerédi’s Regularity Lemma, based on the computation of singular values of matrices. Mathematical Reviews Subject Numbers: 05C85, 68R10.

1 Introduction

“Szemerédi’s Regularity Lemma [9] is one of the most powerful tools of (extremal) graph theory”. One can only agree with that opening sentence of the paper by Komlós and Simonovits [6]. It has many, many applications and we refer the reader to this excellent survey.

∗Supported in part by NSF grant CCR-9530974.

†Supported in part by NSF grant CCR-9528973.

The Regularity lemma is often used to prove the existence of certain objects and if in addition one wants to construct them, then one needs a constructive version of the lemma. This was provided by Alon, Duke, Lefmann, Rödl and Yuster [1]. Subsequently, Frieze and Kannan [3, 4] gave a different version and extended it to deal with hypergraphs, (see also Czygrinow and Rödl [2]).

In this note, we give another construction based on the construction of singular values of matrices. The proofs in [1, 3, 4] are somewhat technical. The result of this paper follows quite easily from a simple lemma relating non-regularity and largeness of singular values.

1.1 Szemerédi’s Lemma

Let G = (V, E) be a graph with n vertices and let A be its adjacency matrix. For a disjoint pair of subsets A, B ⊆ V let e(A, B) denote the number of edges between A and B. The density d(A, B) is defined by

d(A, B) = \frac{e(A, B)}{|A| |B|}.

A disjoint pair A, B ⊆ V is said to be ϵ − regular if for every X ⊆ A with |X| ≥ ϵ|A| and Y ⊆ B with |Y | ≥ ϵ|B|, we have

|d(X, Y) − d(A, B) | ≤ ϵ.

Theorem 1 (Szemerédi’s Regularity Lemma) For every ϵ > 0 and integer m > 0 there are integers P (ϵ, m), Q(ϵ, m) with the following property: for every graph G = (V, E) with n ≥ P (ϵ, m) vertices there is a partition P of V into k + 1 classes V_{0}, V_{1}, …, V_{k} such that

• m ≤ k ≤ Q(ϵ, m).

• |V_{1}| = |V_{2}| = ⋯ = |V_{k}|.

• All but at most ϵk^{2} of the pairs (V_{i}, V_{j}) are ϵ-regular.

• |V_{0}| ≤ ϵn.

A partition satisfying the second criterion is called equitable. V_{0} is called the exceptional class.

Following [9], for every equitable partition P into k + 1 classes we define a number called the index of P.

ind(P) = \frac{1}{k^{2}} ∑_{1≤r,s≤k} d(V_{i}, V_{j})^{2}.

A crucial lemma proved in [9] and stated in the following form in [1] states:

Lemma 1 Fix k and γ and let G = (V, E) be a graph with n vertices. Let P be an equitable partition of V into classes V_{0}, V_{1}, …, V_{k}. Assume |V_{1}| > 4^{2k} and 4^{k} > 600γ^{−2}. Given proofs that more than γk^{2} pairs (V_{r}, V_{s}) are not γ-regular (where by proofs we mean subsets X = X(r, s) ⊆ V_{r}, Y = Y (r, s) =⊆ V_{s} that violate the γ-regularity of (V_{r}, V_{s})) we can 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) + γ^{5}/20.

We first describe a procedure for finding a proof that a pair is not γ-regular; this will be the central part. Then we complete the algorithm with this procedure on hand using the above lemma.

1.2 Singular Values

An m × n matrix A has a Singular Value Decomposition into the sum of rank one matrices, see for example Golub and Van Loan [5]. It has many important applications. The first singular value σ_{1} is defined as

σ_{1}(A) = max_{|x|=|y|=1} |x^{T} Ay|.

This value can be computed with high accuracy in polynomial time [5]. It is the square root of the largest eigenvalue of A^{T} A.

For the following lemma, W is a p × q matrix with rows indexed by R, columns indexed by C. We assume that ||W||_{∞} = max_{i∈R,j∈C} |W(i, j)| ≤ 1.

For S ⊆ R, U ⊆ C we let

W(S, T) = ∑_{i∈S} ∑_{j∈T} W(i, j) = x_{S}^{T}Wx_{U}  (1)

where x_{S} is the 0-1 indicator vector of S i.e. (x_{S})_{i} = 1 iff i ∈ S.

Let A be the adjacency matrix of G. Suppose we now have a partition of V into V_{1}, V_{2}, … and we wish to check whether (V_{r}, V_{s}) form a γ-regular pair for some γ. We let R = V_{r}, C = V_{s} and let A_{r,s} be the R × C submatrix of A corresponding to these rows and columns. Let

d = \frac{1}{|V_{r}| |V_{s}|} ∑_{i∈V_{r}} ∑_{j∈V_{s}} A(i, j)

be the average of the entries in A_{r,s}. Let D be the R × C matrix with all entries equal to d. Let W = W_{r,s} = A_{r,s} − D. Re-phrasing the definition of a regular pair we see that

(V_{r}, V_{s}) is an ϵ-regular pair iff |W(S, T)| ≤ ϵ|S| |T |  (2)

for all S ⊆ R, |S| ≥ ϵ|R|, T ⊆ C, |T | ≥ ϵ|C|.

The following lemma relates this all to σ_{1}(W).

Lemma 2 Let W be an R × C matrix with |R| = p, |C| = q and ||W||_{∞} ≤ 1 and γ be a positive real.

(a) If there exist S ⊆ R, T ⊆ C such that |S| ≥ γp, |T | ≥ γq and |W(S, T)| ≥ γ|S| |T | then σ_{1}(W) ≥ γ^{3}\sqrt{pq}.

(b) If σ_{1}(W) ≥ γ\sqrt{pq} then there exist S ⊆ R, T ⊆ C such that |S| ≥ γ′p, |T | ≥ γ′q and |W(S, T)| ≥ γ′|S| |T | where γ′ = \frac{γ^{3}}{108}. Furthermore S, T can be constructed in polynomial time.

Proof

(a) From (1) we see that

|x_{S}^{T}Wx_{T} | ≥ γ|S| |T | ≥ γ^{3}pq.

Now let ξ_{S} = x_{S}/|x_{S}| and ξ_{T} = x_{T} /|x_{T} |. Then

|ξ_{S}^{T} Wξ_{T} | ≥ γ^{3}pq/(|ξ_{S}| |ξ_{T} |) ≥ γ^{3}\sqrt{pq}

since |x_{S}| ≤ \sqrt{p} and |x_{T} | ≤ \sqrt{q}. This proves (a).

(b) W.l.o.g. we can choose x, y such that x^{T} Wy ≥ γ\sqrt{pq}, |x| = 1, |y| = 1. Let β > 0 (β will be later set to 3/γ) and define x̂ by

x̂_{i} = \{ \begin{matrix}x_{i} : & if |x_{i}| ≤ \frac{β}{\sqrt{p}} \\ 0 : & otherwise \end{matrix}

and define ŷ by a similar truncation at β/\sqrt{q}.

Since |x| = 1 we see that I = \{i : |x_{i}| ≥ β/\sqrt{p}\} has cardinality at most p/β^{2}. Let W_{1} be obtained from W by replacing elements in rows other than I by zero. Then (using the standard inequality that for any vector a and matrix M, we have |a^{T} M| ≤ |a|||M||_{F}, where ||M||_{F}^{2} is the sum of squares of the entries of M)

|(x − x̂)^{T} Wy| = |(x − x̂)^{T} W_{1}y| ≤ |x − x̂|||W_{1}||_{F} |y| ≤ ||W_{1}||_{F} ≤ \frac{\sqrt{pq}}{β} .

By a similar argument we obtain |x̂^{T} W(y − ŷ)| ≤ \sqrt{pq}/β. Thus

x̂^{T} Wŷ = x^{T} Wy − (x − x̂)^{T} Wy − x̂^{T} W(y − ŷ) ≥ (γ − 2/β)\sqrt{pq}.

Let γ̂ = γ − 2/β. Then at least one of (x̂^{+})^{T} Wŷ^{+}, (x̂^{+})^{T} Wŷ^{−}, (x̂^{−})^{T} Wŷ^{+}, (x̂^{−})^{T} Wŷ^{−} is at least γ̂\sqrt{pq}/4. Here ξ^{+} is obtained from ξ ∈ R^{p} by putting ξ_{i}^{+} = max{0, ξ_{i}}. ξ^{−} = −((−ξ)^{+}).

Suppose without loss of generality that (x̂^{+})^{T} Wŷ^{−} ≥ γ̂\sqrt{pq}/4. (The proof for the other cases is similar.) We define random subsets S, T as follows:

For each i ∈ R, put i in S with probability x̂_{i}^{+}\sqrt{p}/β. For each j ∈ C, put j in T with probability −ŷ_{j}^{−}\sqrt{q}/β.

Then

E(W(S, T)) = −(x̂^{+})^{T} Wŷ^{−}(\sqrt{pq}/β^{2}) ≤ −γ̂pq/(4β^{2}).

Thus there exist S, T such that W(S, T) ≤ −γ̂pq/(4β^{2}). Furthermore, such S, T can easily be constructed in O(pq) time using the method of conditional expectations [7] and [8]. Indeed for any r ∈ R we have

E(W(S, T)) = E(W(S, T) | r ∈ S)Pr(r ∈ S)+E(W(S, T) | r ∉ S)Pr(r ∉ S)

and fixing r ∈ S or r ∉ S essentially reduces the size of R by one.

Putting β = 3/γ we get |W(S, T)| ≥ γ^{3}pq/108. We need only verify that S, T are not too small in order to complete the proof of (b). But this follows immediately from |S| |T | ≥ |W(S, T)|. □

We can combine Lemmas 1 and 2 to make an algorithm for finding an ϵregular partition, much as in [1].

1. Arbitrarily divide the vertices of G into an equitable partition P_{1} with classes V_{0}, V_{1}, …, V_{b} where |V_{i}| = ⌊n/b⌋ and hence |V_{0}| < b. denote k_{1} = b.

2. For every pair (V_{r}, V_{s}) of P_{i}, compute σ_{1}(W_{r,s}). If the pair (V_{r}, V_{s}) are not ϵ-regular then by Lemma 2 we obtain a proof that they are not γ = ϵ^{9}/108-regular.

3. If there are at most ϵ\binom{k_{i}}{2} pairs that produce proofs of non γ-regularity then halt. P_{i} is ϵ-regular.

4. Apply Lemma 1 where P = P_{i}, k = k_{i}, γ = ϵ^{9}/108 and obtain a partition P′ with 1 + k_{i}4^{k_{i}} classes.

5. Let k_{i+1} = k_{i}4^{k_{i}}, P_{i+1} = P′, i = i + 1 and go to Step 2.

The algorithm finishes in at most O(ϵ^{−45}) steps with an ϵ-regular partition, since ind ≤ 1/2 and each non-terminating step increases the index by γ^{5}/20 = Ω(ϵ^{45}).

References

[1] N.Alon, R.A.Duke, H.Lefmann, V.Rödl and R.Yuster, The algorithmic aspects of the Regularity Lemma, Journal of Algorithms 16 (1994) 80-109.

[2] A.Czygrinow and V.Rödl, Algorithmic Regularity Lemma for Hypergraphs, in preparation.

[3] A.M.Frieze and R.Kannan, The Regularity Lemma and approximation schemes for dense problems, Proceedings of the 37th Annual IEEE Symposium on Foundations of Computing, (1996) 12-20.

[4] A.M.Frieze and R.Kannan, Quick approximations to matrices and applications, to appear in Combinatorica.

[5] G.H.Golub and C.F.Van Loan, Matrix Computations, Johns Hopkins University Press, London, 1989.

[6] J.Komlós and M.Simonovits, Szemerédi’s regularity Lemma and its applications in graph theory, Combinatorics, Paul Erdős is Eighty, Bolyai Society Mathematical Studies, 2, D.Miklós, V.T.Sós and T.Szőnyi Eds., (1996) 295-352.

[7] P.Raghavan, Probabilistic construction of deterministic algorithms: Approxiamting packing integer programs, Journal of Computer and System Sciences 37 (1988) 130-143.

[8] J.Spencer, Ten lectures on the probabilistic method, SIAM, Philadelphia,1987.

[9] E.Szemerédi, Regular partitions of graphs, Proceedings, Colloque Inter. CNRS (J.-C. Bermond, J.-C.Fournier, M.Las Vergnas and D.Sotteau, Eds.) (1978) 399-401.