Algorithmic Aspects of Regularity

Y. Kohayakawa^{1}^{⋆} and V. Rödl^{2}

1 Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508–900 São Paulo, Brazil

                             yoshi@ime.usp.br

2 Department of Mathematics and Computer Science, Emory University, Atlanta, GA, 30322, USA

                          rodl@mathcs.emory.edu

Abstract. Szemerédi’s celebrated regularity lemma proved to be a fundamental result in graph theory. Roughly speaking, his lemma states that any graph may be approximated by a union of a bounded number of bipartite graphs, each of which is ‘pseudorandom’. As later proved by Alon, Duke, Lefmann, Rödl, and Yuster, there is a fast deterministic algorithm for finding such an approximation, and therefore many of the existential results based on the regularity lemma could be turned into constructive results. In this survey, we discuss some recent developments concerning the algorithmic aspects of the regularity lemma.

1 Introduction

In the course of proving his well known density theorem for arithmetic progressions [47], Szemerédi discovered a fundamental result in graph theory. This result became known as his regularity lemma [48]. For an excellent survey on this lemma, see Komlós and Simonovits [35]. Roughly speaking, Szemerédi’s lemma states that any graph may be approximated by a union of a bounded number of bipartite graphs, each of which is ‘pseudorandom’.

Szemerédi’s proof did not provide an efficient algorithm for finding such an approximation, but it was later proved by Alon, Duke, Lefmann, Rödl, and Yuster [1, 2] that such an algorithm does exist. Given the wide applicability of the regularity lemma, the result of [1, 2] had many consequences. The reader is referred to [1, 2, 14, 35] for the first applications of the algorithmic version of the regularity lemma. For more recent applications, see [5–7, 12, 17, 32, 52].

If the input graph G has n vertices, the algorithm of [1, 2] runs in time O(M(n)), where M(n) = O(n^{2.376}) is the time needed to multiply two n by n matrices with {0, 1}-entries over the integers. In [34], an improvement of this is given: it is shown that there is an algorithm for the regularity lemma that runs in time O(n^{2}) for graphs of order n.

If one allows randomization, one may do a great deal better, as demonstrated by Frieze and Kannan. In fact, they show in [21, 22] that there is a randomized

⋆ Partially supported by FAPESP (Proc. 96/04505–2), by CNPq (Proc. 300334/93–1), and by MCT/FINEP (PRONEX project 107/97).

algorithm for the regularity lemma that runs in time O(n) for n-vertex graphs. Quite surprisingly, they in fact show that one may obtain an implicit description of the required output in constant time. The key technique here is sampling.

The regularity lemma has been generalized for hypergraphs in a few different ways; see, e.g., [8, 18, 19, 21, 22, 42]. One of these generalizations admits constructive versions, both deterministic [13] and randomized [21, 22]. Again, the consequences of the existence of such algorithms are important. For instance, Frieze and Kannan [21, 22] prove that all ‘dense’ MaxSNP-hard problems admit PTAS, by making use of such algorithms. For other applications of an algorithmic hypergraph regularity lemma, see Czygrinow [11].

Let us discuss the organization of this survey. In Section 2, we state the regularity lemma for graphs and hypergraphs. In Section 3, we discuss a few independent lemmas, each of which allows one to produce algorithms for the regularity lemma. In Section 4.1, we state the main result of [34]. Some results of Frieze and Kannan are discussed in Section 4.2. In Section 5, we discuss a recent result on property testing on graphs, due to Alon, Fischer, Krivelevich, and Szegedy [3, 4]. The main result in [3, 4] is based on a new variant of the regularity lemma. We close with some final remarks.

2 The regularity lemma

In this section we state the regularity lemma and briefly discuss the original proof of Szemerédi. In order to be concise, we shall state a hypergraph version that is a straightforward extension of the classical lemma. We remark that this extension was first considered and applied by Prömel and Steger [42].

2.1 The statement of the lemma

Given a set V and a non-negative integer r, we write [V]^{r} for the collection of subsets of V of cardinality r. An r-uniform hypergraph or r-graph on the vertex set V is simply a collection of r-sets H ⊂ [V]^{r}. The elements of H are the hyperedges of H

Let U_{1}, …, U_{r} ⊂ V be pairwise disjoint, non-empty subsets of vertices. The density d_{H}(U_{1}, …, U_{r}) of this r-tuple with respect H is

d_{H}(U_{1}, …, U_{r}) = \frac{e(U_{1}, …, U_{r})}{|U_{1}| … |U_{r}|},  (1)

where e(U_{1}, …, U_{r}) is the number of hyperedges e ∈ H with |e ∩ U_{i}| = 1 for all 1 ≤ i ≤ r. We say that the r-tuple (U_{1}, …, U_{r}) is ε-regular with respect to H if, for all choices of subsets U′_{i} ⊂ U_{i} with |U′_{i}| ≥ ε|U_{i}| for all 1 ≤ i ≤ r, we have

|d_{H}(U′_{1}, …, U′_{r}) − d_{H}(U_{1}, …, U_{r})| ≤ ε.  (2)

If for any such U′_{i} (1 ≤ i ≤ r) we have

|d_{H}(U′_{1}, …, U′_{r}) − α| ≤ δ,  (3)

we say that the r-tuple (U_{1}, …, U_{r}) is (α, δ)-regular. Finally, we say that a partition V = V_{0} ∪ ⋯ ∪ V_{k} of the vertex set V of H is ε-regular with respect to H if

(i) |V_{0}| < ε|V |, (ii) |V_{1}| = ⋯ = |V_{k}|, (iii) at least (1 − ε)\binom{k}{r} of the r-tuples (V_{i_{1}}, …, V_{i_{r}}) with 1 ≤ i_{1} < ⋯ < i_{r} ≤ k

are ε-regular with respect to H.

Often, V_{0} is called the exceptional class of the partition. For convenience, we say that a partition (V_{i})_{i=0}^{k} is (ε, k)-equitable if it satisfies (i) and (ii) above. The hypergraph version of Szemerédi’s lemma reads as follows.

Theorem 1 For any integers r ≥ 2 and k_{0} ≥ 1 and real number ε > 0, there are integers K = K(r, k_{0}, ε) and N = N(r, k_{0}, ε) such that any r-graph H on a vertex set of cardinality at least N admits an (ε, k)-equitable ε-regular partition with k_{0} ≤ k ≤ K.

Szemerédi [48] considered the case r = 2, that is, the case of graphs. However, the proof in [48] generalizes in a straightforward manner to a proof of Theorem 1 above; see Prömel and Steger [42], where the authors prove and apply this result.

2.2 Brief outline of proofs

Let H be an r-graph on the vertex set V with |V | = n, and let Π = (V_{i})_{i=0}^{k} be an (ε, k)-equitable partition of V. A crucial definition in Szemerédi’s proof of his lemma is the concept of the index ind(Π) of Π, given by

ind(Π) = \binom{k}{r}^{−1} ∑ d(V_{i_{1}}, …, V_{i_{r}})^{2},  (4)

where the sum is taken over all r-tuples 1 ≤ i_{1} < ⋯ < i_{r} ≤ k. Clearly, we always have 0 ≤ ind(Π) ≤ 1. For convenience, if Π′ = (W_{j})_{j=0}^{ℓ} is an (ε′, ℓ)-equitable partition of V, we say that Π′ is a refinement of Π if, for any 1 ≤ j ≤ ℓ, there is 1 ≤ i ≤ k for which we have W_{j} ⊂ V_{i}. In words, Π′ refines Π if any nonexceptional class of Π′ is contained in some non-exceptional class of Π. Now, the key lemma in the proof of Theorem 1 is the following (see [42]).

Lemma 2 For any integer r ≥ 2 and real number ε > 0, there exist integers k_{0} = k_{0}(r, ε) and n_{0} = n_{0}(r, ε) and a positive number ϑ = ϑ(r, ε) > 0 for which the following holds. Suppose we have an r-graph H on a vertex V, with n = |V | ≥ n_{0}, and Π = (V_{i})_{i=0}^{k} is an (ε, k)-equitable partition of V. Then

(i) either Π is ε-regular with respect to H, (ii) or, else, there is a refinement Π′ = (W_{j})_{j=0}^{ℓ} of Π such that

(a) |W_{0}| ≤ |V_{0}| + n/4^{k},

(b) |W_{1}| = ⋯ = |W_{ℓ}|, (c) ℓ = k4^{k^{r−1}},

(d) ind(Π′) ≥ ind(Π) + ϑ.

Theorem 1 follows easily from Lemma 2: it suffices to recall that the index can never be larger than 1, and hence if we successively apply Lemma 2, starting from an arbitrary partition Π, we must arrive at an ε-regular partition after a bounded number of steps, because (d) of alternative (ii) guarantees that the indices of the partitions that we generate always increase by a fixed positive amount.

Ideally, to turn this proof into an efficient algorithm, given a partition Π, we would like to have (I) an efficient procedure to check whether (i) applies, and (II) if (i) fails, an efficient procedure for finding Π′ as specified in (a)–(d).

It turns out that if we actually have, at hand, witnesses for the failure of ε-regularity of > ε\binom{k}{r} of the r-tuples (V_{i_{1}}, …, V_{i_{r}}), where 1 ≤ i_{1} < ⋯ < i_{r} ≤ k, then Π′ may be found easily (see [42] for details). Here, by a witness for the εirregularity of an r-tuple (U_{1}, …, U_{r}) we mean an r-tuple (U′_{1}, …, U′_{r}) with U′_{i} ⊂ U_{i} and |U′_{i}| ≥ ε|U_{i}| for all 1 ≤ i ≤ r for which (2) fails. We are therefore led to the following decision problem:

Problem 3 Given an r-graph H, an r-tuple (U_{1}, …, U_{r}) of non-empty, pairwise disjoint sets of vertices of H, and a real number ε > 0, decide whether this r-tuple is ε-regular with respect to H.

In case the answer to Problem 3 is negative for a given instance, we would like to have a witness for the ε-irregularity of the given r-tuple.

3 Conditions for regularity

3.1 A hardness result

It turns out that Problem 3 is hard, as proved by Alon, Duke, Lefmann, Rödl, and Yuster [1, 2].

Theorem 4 Problem 3 is coNP-complete for r = 2.

Let us remark in passing that Theorem 4 is proved in [1, 2] for the case in which ε = 1/2; for a proof for arbitrary 0 < ε ≤ 1/2, see Taraz [49].

Theorem 4 is certainly discouraging. Fortunately, however, there is a way around. We discuss the graph and hypergraph cases separately.

The graph case. In the case r = 2, that is, in the case of graphs, one has the following lemma. Below ℝ_{+} denotes the set of positive reals. Moreover, a bipartite graph B = (U, W; E) with vertex classes U and W and edge set E is said to be ε-regular if (U, W) is an ε-regular pair with respect to B. Thus, a witness to the ε-irregularity of B is a pair (U′, W′) with U′ ⊂ U, W′ ⊂ W, |U′|, |W′| ≥ εn, and |d_{B}(U′, W′) − d_{B}(U, W)| > ε (see the paragraph before Problem 3).

Lemma 5 There is a polynomial-time algorithm A and a function ε′_{A}: ℝ_{+} → ℝ_{+} such that the following holds. When A receives as input a bipartite graph B = (U, W; E) with |U| = |W | = n and a real number ε > 0, it either correctly asserts that B is ε-regular, or else it returns a witness for the ε′_{A}(ε)-irregularity of B.

We remark that Lemma 5 implicitly says that ε′ = ε′_{A}(ε) ≤ ε, for otherwise A would not be able to handle an input graph B that is not ε-regular but is ε′- regular. In fact, one usually has ε′ ≪ ε.

Note that Lemma 5 leaves open what the behaviour of A should be when B is ε-regular but is not ε′-regular. Despite this fact, Lemma 5 does indeed imply the existence of a polynomial-time algorithm for finding ε-regular partitions of graphs. We leave the proof of this assertion as an exercise for the reader.

In Sections 3.2, 3.3, and 3.4 we state some independent results that imply Lemma 5, thus completing the general description of a few distinct ways one may prove the algorithmic version of the regularity lemma for graphs.

The hypergraph case. In the case of r-graphs (r ≥ 3), we do not know a result similar to Lemma 5. The algorithmic version of Theorem 1 for r ≥ 3 is instead proved by introducing a modified concept of index and then by proving a somewhat more complicated version of Lemma 5. For lack of space, we shall not go into details; the interested reader is referred to Czygrinow and Rödl [13]. In fact, in the remainder of this survey we shall mostly concentrate on graphs.

Even though several applications are known for the algorithmic version of Theorem 1 for r ≥ 3 (see, e.g., [11–13, 21, 22]), it should be mentioned that the most powerful version of the regularity lemma for hypergraphs is not the one presented above. Indeed, the regularity lemma for hypergraphs proved in [18] seems to have deeper combinatorial consequences.

3.2 The pair condition for regularity

As mentioned in Section 3.1, Lemma 5 may be proved in a few different ways. One technique is presented in this section. The second, which is in fact a generalization of the methods discussed here, is based on Lemmas 9 and 10. Finally, the third method, presented in Section 3.4, is based on a criterion for regularity given in Lemma 11.

Let us turn to the original approach of [1, 2]. The central idea here may be summarized in two lemmas, Lemmas 6 and 7 below; we follow the formulation given in [14] (see also [9, 20, 50, 51] and the proof of the upper bound in Theorem 15.2 in [16], due to J. H. Lindsey). Below, d(x, x′) denotes the joint degree or codegree of x and x′, that is, the number of common neighbours of x and x′.

Lemma 6 Let a constant 0 < ε < 1 be given and let B = (U, W; E) be a bipartite graph with |U| ≥ 2/ε. Let ϱ = d_{B}(U, W) and let D be the collection of all pairs {x, x′} of vertices of U for which

(i) d(x), d(x′) > (ϱ − ε)|W |, (ii) d(x, x′) < (ϱ + ε)^{2}|W |.

Then if |D| > (1/2)(1 − 5ε)|W |^{2}, the pair (U, W) is (ϱ, (16ε)^{1/5})-regular.

Lemma 7 Let B = (U, W; E) be a graph with (U, W) a (ϱ, ε)-regular pair and with density d(U, W) = ϱ. Assume that ϱ|W | ≥ 1 and 0 < ε < 1. Then

(i) all but at most 2ε|W | vertices x ∈ W satisfy

(ϱ − ε)|W | < d(x), d(x′) < (ϱ + ε)|W |,

(ii) all but at most 2ε|U|^{2} pairs {x, x′} of vertices of A satisfy

d(x, x′) < (ϱ + ε)^{2}|W |.

It is not difficult to see that Lemmas 6 and 7 imply Lemma 5. Indeed, the main computational task that algorithm A from Lemma 5 has to perform is to compute the codegrees of all pairs of vertices (x, x′) ∈ U × U. Clearly, this may be done in time O(n^{3}). Observing that this task may be encoded as the squaring of a certain natural {0, 1}-matrix over the integers, one sees that there is an algorithm A as in Lemma 5 with time complexity O(M(n)), where M(n) = O(n^{2.376}) is the time required to carry out such a multiplication (see [10]).

Before we proceed, let us observe that the pleasant fact here is the following. Although the definition of ε-regularity for a pair (U, W) involves a quantification over exponentially many pairs (U′, W′), we may essentially check the validity of this definition by examining all pairs (x, x′) ∈ U × U, of which there are only quadratically many. We refer to the criterion for regularity given by Lemmas 6 and 7 as the pair condition for regularity.

3.3 An optimized pair condition for regularity

Here we state an improved version of the pair condition of Section 3.2. The key idea is that it suffices to control the codegrees of a small, suitably chosen set of pairs of vertices to guarantee the regularity of a bipartite graph; that is, we need not examine all pairs (x, x′) ∈ U × U. As it turns out, it suffices to consider the pairs that form the edge set of a linear-sized expander, which reduces the number of pairs to examine from \binom{n}{2} to O(n). This implies that there is an algorithm A as in Lemma 5 with time complexity O(n^{2}).

We start with an auxiliary definition.

Definition 8 Let 0 < ϱ ≤ 1 and A > 0 be given. We say that a graph J on n vertices is (ϱ, A)-uniform if for any pair of disjoint sets U, W ⊂ V (J) such that 1 ≤ |U| ≤ |W | ≤ r|U|, where r = ϱn, we have

|e_{J}(U, W) − ϱ|U||W || ≤ A\sqrt{r|U||W |} .

Thus, a (ϱ, A)-uniform graph is a graph with density ∼ ϱ in which the edges are distributed in a random-like manner. One may check that the usual binomial random graph G(n, p) is (p, 20)-uniform (see, e.g., [31]). More relevant to us is the fact that there are efficiently constructible graphs J that are (ϱ, O(1))-uniform, and have arbitrarily large but constant average degree. Here we have in mind the celebrated graphs of Margulis [41] and Lubotzky, Phillips, and Sarnak [39] (see also [40, 46]). For these graphs, we have A = 2.

Let us now introduce the variant of the pair condition for regularity that is of interest. Let an n by n bipartite graph B = (U, W; E) be given, and suppose that J is a graph on U. Write e(J) for the number of edges in J and let p = e(B)/n^{2} be the density of B. We say that B satisfies property P(J, δ) if

∑_{{x,y}∈E(J)} |d(x, y) − p^{2}n| ≤ δp^{2}ne(J).  (5)

Below, we shall only be interested in the case in which J is (ϱ, A)-uniform for some constant A and ϱ ≍ 1/n. The results analogous to Lemmas 6 and 7 involving property P are as follows.

Lemma 9 For every ε > 0, there exist r_{0} = r_{0}(ε), n_{0} = n_{0}(ε) ≥ 1, and δ = δ(ε) > 0 for which the following holds. Suppose n ≥ n_{0}, the graph J is a (ϱ, A)- uniform graph with ϱ = r/n ≥ r_{0}/n, and B is a bipartite graph as above. Then, if B has property P(J, δ), then B is ε-regular.

Lemma 10 For every δ > 0, there exist r_{1} = r_{1}(δ), n_{1} = n_{1}(δ) ≥ 1, and ε′ = ε′(δ) > 0 for which the following holds. Suppose n ≥ n_{1}, the graph J is a (ϱ, A)- uniform graph with ϱ = r/n ≥ r_{1}/n, and B is a bipartite graph as above. Then, if B does not satisfy property P(J, δ), then B is not ε′-regular. Furthermore, in this case, we can find a pair of sets of vertices (U′, W′) witnessing the ε′- irregularity of B in time O(n^{2}).

Lemmas 9 and 10 show that Lemma 5 holds for an algorithm A with time complexity O(n^{2}).

The proof of Lemma 9 is similar in spirit to the proof of Lemma 6, but of course one has to make heavy use of the (ϱ, A)-uniformity of J. The sparse version of the regularity lemma (see, e.g., [33]) may be used to prove the ε′-irregularity of the graph B in Lemma 10. However, proving that a suitable witness may be found in quadratic time requires a different approach. The reader is referred to [34] for details.

3.4 Singular values and regularity

We now present an approach due to Frieze and Kannan [23]. Let an m by n real matrix A be given. The first singular value σ_{1}(A) of A is

σ_{1}(A) = sup{|x^{⊤}Ay|: ||x|| = ||y|| = 1}.  (6)

Above, we use || || to denote the 2-norm. In what follows, for a matrix W = (w_{i,j}), we let ||W||_{∞} = max |w_{i,j}|. Moreover, if I and J are subsets of the index sets of the rows and columns of W, we let

W(I, J) = ∑_{i∈I,j∈J} w_{i,j} = χ_{I}^{⊤}Wχ_{J},  (7)

where χ_{I} and χ_{J} are the {0, 1}-characteristic vectors for I and J.

Let B = (U, W; E) be a bipartite graph with density p = e(B)/|U||W |, and let A = (a_{i,j})_{i∈U,j∈W} be the natural {0, 1}-adjacency matrix associated with B. Put W = A − pJ, where J is the n × n matrix with all entries equal to 1. It is immediate to check that the following holds:

(*) B is ε-regular if and only if |W(U′, W′)| ≤ ε|U′||W′| for all U′ ⊂ U and W′ ⊂ W with |U′| ≥ ε|U| and |W′| ≥ ε|W |.

The regularity condition of Frieze and Kannan [23] is as follows.

Lemma 11 Let W be a matrix whose entries are index by U × W, where |U| = |W | = n, and suppose that ||W||_{∞} ≤ 1. Let γ > 0 be given. Then the following assertions hold:

(i) If there exist U′ ⊂ U and W′ ⊂ W such that |U′|, |W′| ≥ γn and

|W(U′, W′)| ≥ γ|U′||W′|,

then σ_{1}(W) ≥ γ^{3}n. (ii) If σ_{1}(W) ≥ γn, then there exist U′ ⊂ U and W′ ⊂ W such that |U′|,

|W′| ≥ γ′n and |W(U′, W′)| ≥ γ′|U′||W′|, where γ′ = γ^{3}/108. Furthermore, U′ and W′ may be constructed in polynomial time.

Now, in view of (*) and the fact that singular values may be computed in polynomial time (see, e.g., [29]), Lemma 11 provides a proof for Lemma 5.

4 The algorithmic versions of regularity

In this section, we discuss the constructive versions of Theorem 1 for the graph case, that is r = 2. We discuss deterministic and randomized algorithms separately.

4.1 Deterministic algorithms

Our deterministic result, Theorem 12 below, asserts the existence of an algorithm for finding regular partitions that is asymptotically faster than the algorithm due to Alon, Duke, Lefmann, Rödl, and Yuster [1, 2].

Theorem 12 There is an algorithm A that takes as input an integer k_{0} ≥ 1, an ε > 0, and a graph G on n vertices and returns an ε-regular (ε, k)-equitable partition for G with k_{0} ≤ k ≤ K, where K is as Theorem 1. Algorithm A runs in time ≤ Cn^{2}, where C = C(ε, k_{0}) depends only on ε and k_{0}.

Theorem 12 follows from the considerations in Sections 3.1 and 3.3 (see [34] for details).

It is easy to verify that there is a constant ε′ = ε′(ε, k_{0}) such that if e(G) < ε′n^{2}, then any (ε, k_{0})-equitable partition is ε-regular. Clearly, as the time required to read the input is Ω(e(G)) and, as observed above, we may assume that e(G) ≥ ε′n^{2}, algorithm A in Theorem 12 is optimal, apart from the value of the constant C = C(ε, k_{0}).

A typical application of the algorithmic regularity lemma of [1, 2] asserts the existence of a fast algorithm for a graph problem. As it turns out, the running time of such an algorithm is often dominated by the time required for finding a regular partition for the input graph, and hence the algorithm has time complexity O(M(n)). In view of Theorem 12, the existence of quadratic algorithms for these problems may be asserted. Some examples are given in [34].

4.2 Randomized algorithms

We have been discussing deterministic algorithms so far. If we allow randomization, as proved by Frieze and Kannan, a great deal more may be achieved in terms of efficiency [21, 22]. The model we adopt is as follows. We assume that sampling a random vertex from G as well as checking an entry of the adjacency matrix of G both have unit cost.

Theorem 13 There is a randomized algorithm A_{FK} that takes as input an integer k_{0} ≥ 1, an ε > 0, a δ > 0, and a graph G on n vertices and returns, with probability ≥ 1−δ, an ε-regular (ε, k)-equitable partition for G with k_{0} ≤ k ≤ K, where K is as Theorem 1. Moreover, the following assertions hold:

(i) Algorithm A_{FK} runs in time ≤ Cn, where C = C(ε, δ, k_{0}) depends only on ε, δ, and k_{0}.

(ii) In fact, A_{FK} first outputs a collection of vertices of G of cardinality ≤ C′, where C′ = C′(ε, δ, k_{0}) depends only on ε, δ, and k_{0}, and the above ε-regular partition for G may be constructed in linear time from this collection of vertices.

The fact that one is able to construct a regular partition for a graph on n vertices in randomized time O(n) is quite remarkable; this is another evidence of the power of randomization. However, even more remarkable is what (ii) implies: given ε > 0, δ > 0, and k_{0} ≥ 1, there is a uniform bound C′ = C′(ε, δ, k_{0}) on the number of randomly chosen vertices that will implicitly define for us a suitable ε-regular partition of the given graph, no matter how large this input graph is.

Let us try to give a feel on how one may proceed to prove Theorem 13. We shall discuss a lemma that is central in the Frieze–Kannan approach. The idea is that, if a bipartite graph B = (U, W; E) is not ε-regular, then this may be detected, with high probability, by sampling a bounded number of vertices of B. The effectiveness of sampling for detecting “dense spots” in graphs appears already in Goldreich, Goldwasser, and Ron [25, 26], where many constant time algorithms are developed (we shall discuss such matters in Section 5 below).

Let us state the key technical lemma in the proof of Theorem 13. Let an n by n bipartite graph B = (U, W; E) be given. Our aim is to check whether there exist U′ ⊂ U and W′ ⊂ W such that |U′|, |W′| ≥ εn and

|d_{B}(U′, W′) − d_{B}(U, W)| > ε.

Note that this last inequality is equivalent to |e(U′, W′)−p|U′||W′|| > ε|U′||W′|, where p = e(B)/n^{2} is the density of B. In fact, if

|e(U′, W′) − p|U′||W′|| > γn^{2}

holds and γ ≥ ε, then (U′, W′) must be a witness for the ε-irregularity of B.

We are now ready to state the result of Frieze and Kannan that allows one to prove a randomized version of Lemma 5. The reader may wish to compare this result with Lemmas 7 and 10.

Lemma 14 There is a randomized algorithm A that behaves as follows. Let B = (U, W; E) be as above and let γ and δ > 0 be positive reals. Suppose there exist U′ ⊂ U and W′ ⊂ W for which e(U′, W′) > p|U′||W′| + γn^{2} holds. Then, on input B, γ > 0, and δ > 0, algorithm A determines, with probability ≥ 1 − δ, implicitly defined sets U′′ ⊂ U and W′′ ⊂ W with

e(U′′, W′′) > p|U′′||W′′| + \frac{1}{16}γn^{2}.

The running time of A is bounded by some constant C = C(γ, δ) that depends only on γ and δ.

A few comments concerning Lemma 14 are in order. As before, the model here allows for the selection of random vertices of B as well as checking whether two given vertices are adjacent in constant time. In order to define the sets U′′ and W′′, algorithm A returns two sets Z_{1} ⊂ U and Z_{2} ⊂ W, both of cardinality bounded by some constant depending only on γ and δ > 0. Then, U′′ is simply the set of vertices u ∈ U for which e(u, Z_{2}) ≥ p|Z_{2}|. The set W′′ is defined analogously.

Algorithm A of Lemma 14 is extremely simple, and its elegant proof of correctness is based on the linearity of expectation and on well known large deviation inequalities (see Frieze and Kannan [21]).

We close this section mentioning a result complementary to Lemma 14 (see [15] for a slightly weaker statement). Suppose B = (U, W; E) is ε-regular. Then if U′ ⊂ U and W′ ⊂ W are randomly chosen sets of vertices with |U′| = |W′| ≥ M_{0} = M_{0}(ε′, δ), then the bipartite graph B′ = (U′, W′; E′) induced by B on (U′, W′) is ε′-regular with probability ≥ 1 − δ, as long as ε ≤ ε_{0}(ε′, δ). Here again the striking fact is that a bounded sample of vertices forms a good enough picture of the whole graph.

5 Property testing

The topic of this section is in nature different from the topics discussed so far. We have been considering how to produce algorithms for finding regular partitions of graphs. In this section, we discuss how non-constructive versions of the regularity lemma may be used to prove the correctness of certain algorithms. We shall discuss a recent result to Alon, Fischer, Krivelevich, and Szegedy [3, 4]. These authors develop a new variant of the regularity lemma and use it to prove a far reaching result concerning the testability of certain graph properties.

5.1 Definitions and the testability result

The general notion of property testing was introduced by Rubinfeld and Sudan [45], but in the context of combinatorial testing it is the work of Goldreich and his co-authors [24–28] that are most relevant to us.

Let G^{n} be the collection of all graphs on a fixed n-vertex set, say [n] = {1, …, n}. Put G = ⋃_{n≥1} G^{n}. A property of graphs is simply a subset P ⊂ G that is closed under isomorphisms. There is a natural notion of distance in each G^{n}, the normalized Hamming distance: the distance d(G, H) = d_{n}(G, H) between two graphs G and H ∈ G^{n} is |E(G) △ E(H)|\binom{n}{2}^{−1}, where E(G) △ E(H) denotes the symmetric difference of the edge sets of G and H.

We say that a graph G is ε-far from having property P if

d(G, P) = min_{H∈P} d(G, H) ≥ ε,

that is, at least ε\binom{n}{2} edges have to be added or removed to G to turn it into a graph that satisfies P.

An ε-test for a graph property P is a randomized algorithm A that receives as input a graph G and behaves as follows: if G has P then with probability ≥ 2/3 we have A(G) = 1, and if G is ε-far from having P then with probability ≥ 2/3 we have A(G) = 0. The graph G is given to A through an oracle; we assume that A is able to generate random vertices from G and it may query the oracle whether two vertices that have been generated are adjacent.

We say that a graph property P is testable if, for all ε > 0, it admits an ε-test that makes at most Q queries to the oracle, where Q = Q(ε) is a constant that depends only on ε. Note that, in particular, we require the number of queries to be independent of the order of the input graph.

Goldreich, Goldwasser, and Ron [25, 26], besides showing that there exist NP graph properties that are not testable, proved that a large class of interesting graph properties are testable, including the property of being k-colourable, of having a clique with ≥ ϱn vertices, and of having a cut with ≥ ϱn^{2} edges, where n is the order of the input graph. The regularity lemma is not used in [25, 26]. The fact that k-colourability is testable had in fact been proved implicitly in [15], where regularity is used.

We are now ready to turn to the result of Alon, Fischer, Krivelevich, and Szegedy [3, 4]. Let us consider properties from the first order theory of graphs.

Thus, we are concerned with properties that may be expressed through quantification of vertices, Boolean connectives, equality, and adjacency. Of particular interest are the properties that may be expressed in the form

∃x_{1}, …, x_{r} ∀y_{1}, …, y_{s} A(x_{1}, …, x_{r}, y_{1}, …, y_{s}),

where A is a quantifier-free first order expression. Let us call such properties of type ∃∀. Similarly, we define properties of type ∀∃. The main result of [3, 4] is as follows.

Theorem 15 All first order properties of graphs that may be expressed with at most one quantifier as well as all properties that are of type ∃∀ are testable. Furthermore, there exist properties of type ∀∃ that are not testable.

The first part of the proof of the positive result in Theorem 15 involves the reduction, up to testability, of properties of type ∃∀ to a certain generalized colourability property. A new variant of the regularity lemma is then used to handle this generalized colouring problem.

5.2 A variant of the regularity lemma

In this section we shall state a variant of the regularity lemma proved in [3, 4].

Let us say that a partition Π = (V_{i})_{i=1}^{k} of a set V is an equipartition of V if all the sets V_{i} (1 ≤ i ≤ k) differ by at most 1 in size. In this section, we shall not have exceptional classes in our partitions. Below, we shall have an equipartition of V

Π′ = {V_{i,j}: 1 ≤ i ≤ k, 1 ≤ j ≤ ℓ}

that is a refinement of a given partition Π = (V_{i})_{i=1}^{k}. In this notation, we understand that, for all i, all the V_{i,j} (1 ≤ j ≤ ℓ) are contained in V_{i}.

Theorem 16 For every integer k_{0} and every function 0 < ε(r) < 1 defined on the positive integers, there are constants K = K(k_{0}, ε) and N = N(k_{0}, ε) with the following property. If G is any graph with at least N vertices, then there exist equipartitions Π = (V_{i})_{1≤i≤k} and Π′ = (V_{i,j})_{1≤i≤k, 1≤j≤ℓ} of V = V (G) such that the following hold:

(i) |Π| = k ≥ k_{0} and |Π′| = kℓ ≤ K; (ii) at least (1−ε(0))\binom{k}{2} of the pairs (V_{i}, V_{i′}) with 1 ≤ i < i′ ≤ k are ε(0)-regular; (iii) for all 1 ≤ i < i′ ≤ k, we have that at least (1−ε(k))ℓ^{2} of the pairs (V_{i,j}, V_{i′,j′})

with j, j′ ∈ [ℓ] are ε(k)-regular; (iv) for at least (1 − ε(0))\binom{k}{2} of the pairs 1 ≤ i < i′ ≤ k, we have that for at

least (1 − ε(0))ℓ^{2} of the pairs j, j′ ∈ [ℓ] we have

|d_{G}(V_{i}, V_{i′}) − d_{G}(V_{i,j}, V_{i′,j′})| ≤ ε(0).

Suppose we have partitions Π and Π′ as in Theorem 16 above and that ε(k) ≪ 1/k. It is not difficult to see that then, for many ‘choice’ functions j: [k] → [ℓ], we have that Π̃ = (V_{i,j(i)})_{1≤i≤k} is an equipartition of an induced subgraph of G such that the following hold:

(a) all the pairs (V_{i,j(i)}, V_{i′,j(i′)}) are ε(k)-regular,

(b) for at least (1 − ε(0))\binom{k}{2} of the pairs 1 ≤ i < i′ ≤ k, we have

|d_{G}(V_{i}, V_{i′}) − d_{G}(V_{i,j(i)}, V_{i′,j(i′)})| ≤ ε(0).

In a certain sense, this consequence of Theorem 16 lets us ignore the irregular pairs in the partition Π, at the expense of dropping down from the V_{i} to smaller sets V_{i,j(i)} (still all of cardinality Ω(n)), and having most but not necessarily all densities d_{G}(V_{i,j(i)}, V_{i′,j(i′)}) under tight control.

Let us remark in passing that, naturally, one may ask whether Theorem 1 may be strengthened by requiring that there should be no irregular pairs altogether. This question was already raised by Szemerédi in [48]. As observed by Lovász, Seymour, Trotter, and the authors of [2] (see p. 82 in [2]), such an extension of Theorem 1 does not exist. As noted above, Theorem 16 presents a way around this difficulty.

Theorem 16 and its corollary mentioned above are the main ingredients in the proof of the following result (see [3, 4] for details).

Theorem 17 For every ε > 0 and h ≥ 1, there is δ = δ(ε, h) > 0 for which the following holds. Let H be an arbitrary graph on h vertices and let P = Forb_{ind}(H) be the property of not containing H as an induced subgraph. If an n-vertex graph G is ε-far from P, then G contains δn^{h} induced copies of H.

The case in which H is a complete graph follows from the original regularity lemma, but the general case requires the corollary to Theorem 16 discussed above. Note that Theorem 17 immediately implies that the property of membership in Forb_{ind}(H) (in order words, the property of not containing an induced copy of H) is a testable property for any graph H.

The proof of Theorem 15 requires a generalization of Theorem 17 related to the colouring problem alluded to at the end of Section 5.1. We refer the reader to [3, 4]. We close by remarking that Theorem 16 has an algorithmic version, although we stress that this is not required in the proof of Theorem 15.

6 Concluding remarks

We have not discussed a few recent, important results that relate to the regularity lemma. We single out three topics that the reader may wish to pursue.

6.1 Constants

The constants involved in Theorem 1 are extremely large. The proof in [48] gives that K in Theorem 1 is bounded from above by a tower of 2s of height ε^{−5}. A recent result of Gowers [30] in fact shows that this cannot be essentially improved. Indeed, it is proved in [30] that there are graphs for which any εregular partition must have at least G(ε^{−c}) parts, where c > 0 is some absolute constant and G(x) is a tower of 2s of height ⌊x⌋.

The size of K is very often not too relevant in applications, but in certain cases essentially better results may be obtained if one is able to avoid the appearance of such huge constants. In view of Gowers’s result, this can only be accomplished by modifying the regularity lemma. One early instance in which this carried out appears in [14]; a more recent example is [21].

6.2 Approximation schemes for dense problems

Frieze and Kannan have developed variants of the regularity lemma for graphs and hypergraphs and discuss several applications in [21, 22]. The applications are mostly algorithmic and focus on ‘dense’ problems, such as the design of a PTAS for the max-cut problem for dense graphs. The algorithmic versions of their variants of the regularity lemma play a central rôle in this approach.

For more applications of algorithmic regularity to ‘dense’ problems, the reader is referred to [11–13, 32]

6.3 The blow-up lemma

We close with an important lemma due to Komlós, Sárközy, and Szemerédi [37], the so-called blow-up lemma. (For an alternative proof of this lemma, see [44].)

In typical applications of the regularity lemma, once a suitably regular partition of some given graph G is found, one proceeds by embedding some ‘target graph’ H of bounded degree into G. Until recently, the embedding techniques could only handle graphs H with many fewer vertices than G. The blow-up lemma is a novel tool that allows one to embed target graphs H that even have the same number of vertices as G. The combined use of the regularity lemma and the blow-up lemma is a powerful new machinery in graph theory. The reader is referred to Komlós [36] for a discussion on the applications of the blow-up lemma.

On the algorithmic side, the situation is good: Komlós, Sárközy, and Szemerédi [38] have also proved an algorithmic version of the blow-up lemma (see Rödl, Ruciński, and Wagner [43] for an alternative proof).

References

1. N. Alon, R. A. Duke, H. Lefmann, V. Rödl, and R. Yuster, The algorithmic aspects of the regularity lemma (extended abstract), 33rd Annual Symposium on Foundations of Computer Science (Pittsburgh, Pennsylvania), IEEE Comput. Soc. Press, 1992, pp. 473–481.

2. , The algorithmic aspects of the regularity lemma, Journal of Algorithms 16 (1994), no. 1, 80–109.

3. N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy, Efficient testing of large graphs, submitted, 22pp., 1999.

4. , Efficient testing of large graphs (extended abstract), 40th Annual Symposium on Foundations of Computer Science (New York City, NY), IEEE Comput. Soc. Press, 1999, pp. 656–666.

5. N. Alon and E. Fischer, Refining the graph density condition for the existence of almost K-factors, Ars Combinatoria 52 (1999), 296–308.

6. N. Alon and R. Yuster, Almost H-factors in dense graphs, Graphs and Combinatorics 8 (1992), no. 2, 95–102.

7. , H-factors in dense graphs, Journal of Combinatorial Theory, Series B 66 (1996), no. 2, 269–282.

8. F. R. K. Chung, Regularity lemmas for hypergraphs and quasi-randomness, Random Structures and Algorithms 2 (1991), no. 1, 241–252.

9. F. R. K. Chung, R. L. Graham, and R. M. Wilson, Quasi-random graphs, Combinatorica 9 (1989), no. 4, 345–362.

10. D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions., Journal of Symbolic Computation 9 (1990), no. 3, 251–280.

11. A. Czygrinow, Partitioning problems in dense hypergraphs, submitted, 1999.

12. A. Czygrinow, S. Poljak, and V. Rödl, Constructive quasi-Ramsey numbers and tournament ranking, SIAM Journal on Discrete Mathematics 12 (1999), no. 1, 48–63.

13. A. Czygrinow and V. Rödl, An algorithmic regularity lemma for hypergraphs, submitted, 1999.

14. R. A. Duke, H. Lefmann, and V. Rödl, A fast approximation algorithm for computing the frequencies of subgraphs in a given graph, SIAM Journal on Computing 24 (1995), no. 3, 598–620.

15. R. A. Duke and V. Rödl, On graphs with small subgraphs of large chromatic number, Graphs and Combinatorics 1 (1985), no. 1, 91–96.

16. P. Erdős and J. Spencer, Probabilistic methods in combinatorics, Akademiai Kiado, Budapest, 1974, 106pp.

17. E. Fischer, Cycle factors in dense graphs, Discrete Mathematics 197/198 (1999), 309–323, 16th British Combinatorial Conference (London, 1997).

18. P. Frankl and V. Rödl, Extremal problems on set systems, Random Structures and Algorithms, to appear.

19. , The uniformity lemma for hypergraphs, Graphs and Combinatorics 8 (1992), no. 4, 309–312.

20. P. Frankl, V. Rödl, and R. M. Wilson, The number of submatrices of a given type in a Hadamard matrix and related results, Journal of Combinatorial Theory, Series B 44 (1988), no. 3, 317–328.

21. A. Frieze and R. Kannan, The regularity lemma and approximation schemes for dense problems, 37th Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996), IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, pp. 12–20.

22. , Quick approximation to matrices and applications, Combinatorica 19 (1999), no. 2, 175–220.

23. , A simple algorithm for constructing Szemerédi’s regularity partition, Electronic Journal of Combinatorics 6 (1999), no. 1, Research Paper 17, 7 pp. (electronic).

24. O. Goldreich, Combinatorial property testing (a survey), Randomization methods in algorithm design (Princeton, NJ, 1997), Amer. Math. Soc., Providence, RI, 1999, pp. 45–59.

25. O. Goldreich, S. Goldwasser, and D. Ron, Property testing and its connection to learning and approximation, 37th Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996), IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, pp. 339–348.

26. , Property testing and its connection to learning and approximation, Journal of the Association for Computing Machinery 45 (1998), no. 4, 653–750.

27. O. Goldreich and D. Ron, Property testing in bounded degree graphs, 29th ACM Symposium on Theory of Computing (El Paso, Texas), 1997, pp. 406–419.

28. , A sublinear bipartiteness tester for bounded degree graphs, Combinatorica 19 (1999), no. 3, 335–373.

29. G. H. Golub and C. F. van Loan, Matrix computations, Johns Hopkins University Press, London, 1989.

30. W. T. Gowers, Lower bounds of tower type for Szemerédi’s uniformity lemma, Geometric and Functional Analysis 7 (1997), no. 2, 322–337.

31. P. E. Haxell, Y. Kohayakawa, and T. Łuczak, The induced size-Ramsey number of cycles, Combinatorics, Probability, and Computing 4 (1995), no. 3, 217–239.

32. P. E. Haxell and V. Rödl, Integer and fractional packings in dense graphs, submitted, 1999.

33. Y. Kohayakawa, Szemerédi’s regularity lemma for sparse graphs, Foundations of Computational Mathematics (Berlin, Heidelberg) (F. Cucker and M. Shub, eds.), Springer-Verlag, January 1997, pp. 216–230.

34. Y. Kohayakawa, V. Rödl, and L. Thoma, An optimal deterministic algorithm for Szemerédi’s regularity lemma, submitted, 2000.

35. J. Komlós and M. Simonovits, Szemerédi’s regularity lemma and its applications in graph theory, Combinatorics—Paul Erdős is eighty, vol. 2 (Keszthely, 1993) (D. Miklós, V. T. Sós, and T. Szőnyi, eds.), Bolyai Society Mathematical Studies, vol. 2, János Bolyai Mathematical Society, Budapest, 1996, pp. 295–352.

36. J. Komlós, The blow-up lemma, Combinatorics, Probability and Computing 8 (1999), no. 1-2, 161–176, Recent trends in combinatorics (Mátraháza, 1995).

37. J. Komlós, G. N. Sárközy, and E. Szemerédi, Blow-up lemma, Combinatorica 17 (1997), no. 1, 109–123.

38. , An algorithmic version of the blow-up lemma, Random Structures and Algorithms 12 (1998), no. 3, 297–312.

39. A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), 261–277.

40. A. Lubotzky, Discrete groups, expanding graphs and invariant measures, Birkhäuser Verlag, Basel, 1994, with an appendix by Jonathan D. Rogawski.

41. G. A. Margulis, Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators, Problemy Peredachi Informatsii 24 (1988), no. 1, 51–60.

42. H. J. Prömel and A. Steger, Excluding induced subgraphs III. A general asymptotic, Random Structures and Algorithms 3 (1992), no. 1, 19–31.

43. V. Rödl, A. Ruciński, and M. Wagner, An algorithmic embedding of graphs via perfect matchings, Randomization and approximation techniques in computer science, Lecture Notes in Computer Science, vol. 1518, 1998, pp. 25–34.

44. V. Rödl and A. Ruciński, Perfect matchings in ε-regular graphs and the blow-up lemma, Combinatorica 19 (1999), no. 3, 437–452.

45. R. Rubinfeld and M. Sudan, Robust characterizations of polynomials with applications to program testing, SIAM Journal on Computing 25 (1996), no. 2, 252–271.

46. P. Sarnak, Some applications of modular forms, Cambridge University Press, Cambridge, 1990.

47. E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arithmetica 27 (1975), 199–245, collection of articles in memory of Juriĭ Vladimirovič Linnik.

48. , Regular partitions of graphs, Problèmes Combinatoires et Théorie des Graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) (Paris), Colloques Internationaux CNRS n. 260, 1978, pp. 399–401.

49. A. R. Taraz, Szemerédis Regularitätslemma, April 1995, Diplomarbeit, Universität Bonn, 83pp.

50. A. G. Thomason, Pseudorandom graphs, Random graphs ’85 (Poznań, 1985), North-Holland Math. Stud., vol. 144, North-Holland, Amsterdam–New York, 1987, pp. 307–331.

51. , Random graphs, strongly regular graphs and pseudorandom graphs, Surveys in Combinatorics 1987 (C. Whitehead, ed.), London Mathematical Society Lecture Note Series, vol. 123, Cambridge University Press, Cambridge–New York, 1987, pp. 173–195.

52. A. Tiskin, Bulk-synchronous parallel multiplication of Boolean matrices, Automata, languages and programming, Lecture Notes in Computer Science, vol. 1443, 1998, pp. 494–506.