An optimal algorithm for checking regularity (Extended Abstract) ^{∗}

Y. Kohayakawa ^{†}  V. Rödl ^{‡}  L. Thoma ^{§}

Abstract

We present a deterministic algorithm A that, in O(m^{2}) time, verifies whether a given m by m bipartite graph G is regular, in the sense of Szemerédi [18]. In the case in which G is not regular enough, our algorithm outputs a witness to this irregularity. Algorithm A may be used as a subroutine in an algorithm that finds an ε-regular partition of a given n-vertex graph Γ in time O(n^{2}). This time complexity is optimal, up to a constant factor, and improves upon the bound O(M(n)), proved by Alon, Duke, Lefmann, Rödl, and Yuster [1, 2], where M(n) = O(n^{2.376}) is the time required to square a 0–1 matrix over the integers.

Our approach is elementary, except that it makes use of linear-sized expanders to accomplish a suitable form of deterministic sampling.

1 Introduction and the Main Result Szemerédi’s regularity lemma [18] is a fundamental result in graph theory (see [15] for an excellent survey). Roughly speaking, this lemma states that any graph admits a partition of its vertex set so that most pairs induce ‘pseudorandom’ or regular bipartite graphs. The original proof of the regularity lemma was non-constructive, but Alon, Duke, Lefmann, Rödl, and Yuster [1, 2] succeeded in developing a fast deterministic algorithm for finding such a partition. Many of the existential results based on the regularity lemma could then be turned into algorithmic results. The algorithm in [1, 2] finds a regular partition of an n-vertex graph in O(M(n)) deterministic time, where M(n) = O(n^{2.376}) (see [7]) is the time required to square a 0– 1 matrix over the integers. More recently, Frieze and Kannan [9] (see also [10]) showed that sampling can

∗The first author was partially supported by MCT/CNPq through ProNEx Programme (Proc. CNPq 664107/1997–4), by CNPq (Proc. 300334/93–1 and 468516/2000–0), and by FAPESP (Proj. 96/04505–2). The second author was partially supported by NSF Grant 0071261. The third author was partially supported by NSF grant DMS–9970622. The collaboration of these authors is supported by a CNPq/NSF cooperative grant.

†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

‡Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA. rodl@mathcs.emory.edu

§Department of Mathematics, University of Rhode Island, Kingston RI 02881, USA. thoma@math.uri.edu

be used to develop a O(n) time randomized algorithm that, given an n-vertex graph G, outputs a partition for G that is regular with high probability.

In both algorithms above (and in all algorithms for variants of the regularity lemma), the main algorithmic problem is to decide whether a given m by m bipartite graph G is regular; if G is not regular, we are required to find a ‘witness’ for this irregularity. In this extended abstract, we present a deterministic algorithm that solves this problem in O(m^{2}) time. This algorithm immediately gives an algorithm for Szemerédi’s regularity lemma that finds a regular partition of an n-vertex graph in time O(n^{2}). A key feature of our approach lies in the use of linear-sized expanders for carrying out a certain procedure that may be thought of as deterministic sampling.

1.1 The main result. Let G = (V_{1}, V_{2}; E) be a bipartite graph. If ∅ ≠ U_{i} ⊂ V_{i} (i = 1, 2), the density of (U_{1}, U_{2}) in G is d(U_{1}, U_{2}) = e(U_{1}, U_{2})/|U_{1}||U_{2}|, where we write e(U_{1}, U_{2}) for the number of edges with one endpoint in U_{1} and the other endpoint in U_{2}. We say that G is ε-regular if, for all U_{i} ⊂ V_{i} (i = 1, 2) with |U_{i}| ≥ ε|V_{i}|, we have

|d(U_{1}, U_{2}) − d(V_{1}, V_{2})| ≤ ε. (1.1)

If G is not ε-regular and a certain pair (U_{1}, U_{2}) certifies this fact, then we say that (U_{1}, U_{2}) is a witness to the ε-irregularity of G. If Γ = (V, E) is a graph and V = ⋃_{i=1}^{k} V_{i} is a partition of V such that ||V_{i}| − |V_{j}|| ≤ 1 for all i and j, then we say that the partition (V_{i})_{i=1}^{k} is an ε-regular partition for Γ if ≥ (1 − ε)\binom{k}{2} pairs (V_{i}, V_{j}), where 1 ≤ i < j ≤ k, are ε-regular. We say that a pair (U, W) is ε-regular if the bipartite graph induced by (U, W) is ε-regular.

Szemerédi’s remarkable result may be stated as follows.

Theorem 1.1. For any ε > 0 and any k_{0} ≥ 1, there is K_{0}(ε, k_{0}) such that any graph Γ admits an ε-regular partition into k parts for some k satisfying k_{0} ≤ k ≤ K_{0}(ε, k_{0}).

The algorithmic version of Theorem 1.1, due to Alon, Duke, Lefmann, Rödl, and Yuster [1, 2], may be stated as follows.

Theorem 1.2. There is a deterministic algorithm A_{0} that, given ε > 0, k_{0} ≥ 1, and Γ, produces an εregular partition for Γ into k parts for some k satisfying k_{0} ≤ k ≤ K′_{0}, where K′_{0} = K′_{0}(ε, k_{0}) depends only on ε and k_{0}. Moreover, algorithm A_{0} runs in time O(M(n)) = O(n^{2.376}) if Γ has n vertices.

Consider now the following closely related decision problem.

Problem. Given a graph G, a pair (U, W) of nonempty, pairwise disjoint sets of vertices of G, and a positive ε, decide whether (U, W) is ε-regular with respect to G.

As it turns out, the problem above is coNP-complete [1, 2]. However, as observed already in [1, 2], to prove Theorem 1.2, it suffices to solve an approximate version of the decision problem above. For instance, the following result [8] suffices.

Theorem 1.3. There exists an algorithm A_{1} for which the following holds. When A_{1} receives as input an ε > 0 and a bipartite graph G = (V_{1}, V_{2}; E) with |V_{1}| = |V_{2}| = m ≥ (2/ε)^{5}, it either correctly asserts that G is εregular, or else it returns a witness for the ε′-irregularity of G, where ε′ = ε′_{A_{1}}(ε) = ε^{5}/16. The running time of A_{1} is O(M(m)) = O(m^{2.376}).

(See Frieze and Kannan [11] for a somewhat different approach to verifying regularity, based on singular values of matrices.) Our main result is an improvement of Theorem 1.3 above, and may be stated as follows.

Theorem 1.4. (The main result) There exists an algorithm A for which the following holds. When A receives as input an ε > 0 and a bipartite graph G = (V_{1}, V_{2}; E) with |V_{1}| = |V_{2}| = m ≥ m_{0}(ε), it either correctly asserts that G is ε-regular, or else it returns a witness for the ε′-irregularity of G, where ε′ = ε′_{A}(ε) = ε^{20}/5^{4}2^{32}. The running time of A is O(m^{2}).

We describe our algorithm A in §2.2. Deriving an algorithm for the regularity lemma from Theorem 1.4 is standard, and we omit the details.

Corollary 1.1. There is a deterministic algorithm A′_{0} that, given ε > 0, k_{0} ≥ 1, and a graph Γ, produces an ε-regular partition for Γ into k parts for some k satisfying k_{0} ≤ k ≤ K′′_{0}, where K′′_{0} = K′′_{0}(ε, k_{0}) depends only on ε and k_{0}. Moreover, algorithm A′_{0} runs in time O(n^{2}) if Γ has n vertices.

Clearly, Algorithm A′_{0} above has optimal time complexity, up to the constant implicit in the big-O notation. In [1, 2], several algorithmic consequences are derived from Theorem 1.2. In the examples presented there, the time complexity of the algorithms is O(M(n)). Using A′_{0} from Corollary 1.1, one obtains algorithms with optimal time complexity O(n^{2}). We also observe that a similar improvement may be obtained from Theorem 1.4 for the subgraph counting algorithm given in Duke, Lefmann, and Rödl [8]. We explicitly state examples of these improvements at the end of this introduction.

Let us also mention that an important variant of the regularity lemma, suitable for finding induced subgraphs, was recently discovered by Alon, Fischer, Krivelevich, and Szegedy [3, 4], in the context of property testing (see, e.g., [12] and [13, 14]). In the applications of their regularity lemma in [3, 4], the authors do not need algorithms for finding their regular partitions; however, they observe that an algorithmic version of their lemma readily follows from results such as Theorem 1.3. Again, a O(n^{2}) time algorithm follows immediately from Theorem 1.4.

Finally, we mention that one may prove a ‘nonbipartite version’ of Theorem 1.4. This variant of our result implies that one may check in time O(n^{2}) whether a given n-vertex graph Γ is quasi-random, in the sense of Chung, Graham, and Wilson [6]. Moreover, if Γ is not quasi-random, then our algorithm will produce a suitable witness proving this (an induced subgraph with Ω(n) vertices whose density deviates substantially from the density of Γ).

Local conditions for regularity. One may prove Theorem 1.3 by considering a certain ‘local condition’ on G = (V_{1}, V_{2}; E), |V_{1}| = |V_{2}| = m, that is essentially equivalent to the regularity of G. For simplicity, let us suppose that G is degree-regular. The condition is simply that the following inequality should hold:

∑_{x, y∈V_{1}} |d_{G}(x, y) − p(G)^{2}m| ≤ δp(G)^{2}m , (1.2)

where d_{G}(x, y) = |N_{G}(x) ∩ N_{G}(y)| is the so-called codegree of x and y, and p(G) = |E|/|V_{1}||V_{2}| = |E|/m^{2} is the density of G. Clearly, inequality (1.2) may be checked in O(m^{3}) time, and, in fact, using fast matrix multiplication, one may verify (1.2) in O(M(m)) = O(m^{2.376}) time. The precise meaning of the equivalence of the ε-regularity of G and the validity of (1.2) is as follows: for all ε > 0 there is δ > 0 such that if (1.2) holds, then G is ε-regular. Moreover, for all δ > 0, there is ε′ > 0 such that if (1.2) fails then G is not ε′-regular, and, in fact, a witness to this ε′-irregularity may be constructed explicitly. Some of the ideas described in this paragraph have appeared in the literature under many guises—basically, we are obtaining a somewhat surprising amount of information from ‘pairwise independence’. We do not go into details here.

The key idea in the proof of Theorem 1.4 is that we may restrict the sum in (1.2) to a small, randomly selected collection of pairs {x, y} (and, naturally, scale down the right-hand side). This would not be so satisfactory, as we would have a randomized procedure: we in fact show that we may achieve the same effect by ‘deterministic sampling’, using the edge set of a linearsized expander J (see the definition of property P(J, δ) in §2.2.3).

Algorithmic applications. As we stated above, our algorithm immediately implies an improvement on deterministic algorithms which are based on the Szemerédi regularity lemma. Here we present three typical examples of algorithms for finding and counting given subgraphs. For more algorithmic applications of the regularity lemma see [2] and [8].

The first two propositions describe problems of finding specific subgraphs in a given graph.

Proposition. For every ε > 0 and every integer h, there exists a positive integer n_{0} = n_{0}(ε, h) such that for every graph H with h vertices and chromatic number χ(H), there exists a deterministic algorithm of time complexity O(n^{2}) that, given a graph G = (V, E) with n > n_{0} vertices and minimum degree d > \frac{χ(H)−1}{χ(H)} · n, finds a set of (1 − ε)\frac{n}{h} vertex disjoint copies of H in G.

For the proof of existence see [5].

Proposition. Let k ≥ 3 be an integer and c > 0, ε > 0 be constants. Then there exists an integer n_{0} = n_{0}(k, ε) and a function f(k, ε) such that if G = (V, E) is a graph with n ≥ n_{0} vertices and cn^{2} edges, then either

(i) there exists a subgraph G′ = (V′, E′) of G with χ(G′) ≥ k and |V′| ≤ f(k, ε), or

(ii) there exists a set E′′ ⊆ E with |E′′| ≤ εn^{2} such that the subgraph G′′ = (V, E \ E′′) satisfies χ(G′′) ≤ k − 1.

Furthermore, there is an algorithm that receives as input a graph G = (V, E) as above and has running time O(n^{2}) which either outputs a subgraph G′ as in (i) or a set of edges E′′ as in (ii), together with a proper coloring Δ : V → {1, …, k − 1} of the subgraph G′′.

For the algorithms proving both propositions above see [2].

To describe our third example let us introduce some notation. We will follow [8]. Let G = (V, E) be a labeled graph on n vertices whose vertex set V = {v_{1}, …, v_{n}} is ordered by v_{1} < ⋯ < v_{n}. Let the set W = {w_{1}, …, w_{k}}, k ≤ n, be ordered by w_{1} < ⋯ < w_{k}. We say that a graph H with vertex set W is order isomorphic to an induced subgraph H′ of G if there exists an isomorphism ϕ : H → H′ with the property that for each i and j, 1 ≤ i, j ≤ n, if w_{i} < w_{j}, then ϕ(w_{i}) < ϕ(w_{j}). Let H_{1}, …, H_{t}, where t = 2^{\binom{k}{2}}, be a list of all labeled graphs on the set W and let σ_{k}(G) = (h_{1}, …, h_{t}) be the t-dimensional vector in which for each i, 1 ≤ i ≤ t, h_{i} is the number of induced subgraphs of G to which H_{i} is order isomorphic.

The following proposition asserts the existence of a certain type of approximation algorithm for the vector σ_{k}(G). For more details, see [8].

Proposition. Let k ≥ 4 be in integer. There is an algorithm whose input is a labeled, ordered graph on n vertices and a list of all labeled graphs on an ordered set of k vertices and whose output in an approximation \overline{σ}_{k}(G) = (\overline{h}_{1}, …, \overline{h}_{t}), t = 2^{\binom{k}{2}}, to the vector σ_{k}(G) = (h_{1}, …, h_{t}) with the property that ∑_{1≤i≤t} |h_{i} − \overline{h}_{i}| ≤ \frac{1}{t} ∑_{1≤i≤t} h_{i} . The algorithm runs in O(n^{2+1/ log log n}) time.

2 Preliminaries and the Algorithm 2.1 Auxiliary results on expander graphs. Let 0 < ϱ ≤ 1 and L > 0 be fixed. We say that a graph J on m vertices is (ϱ, L)-uniform if, for any U, W ⊂ V (J) such that U ∩ W = ∅ and 1 ≤ |U| ≤ |W | ≤ r|U|, where r = ϱm, we have

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

Here e_{J}(U, W) stands for the number of edges between the sets U and W in the graph J. The celebrated Ramanujan graphs of Lubotzky, Phillips, and Sarnak [16, 17] are explicitly constructible examples of linear-sized (ϱ, 2)-uniform graphs. We shall make crucial use of the fact that linear-sized (ϱ, O(1))-uniform graphs may be constructed efficiently.

The following three lemmas are easy.

Lemma 2.1. Let R = (V, E) be a (ϱ, L)-uniform, nvertex graph and let ∅ ≠ A ⊂ V be given. Put J = R[A], i.e., J is the subgraph of R induced on the set A. Then J is an (ϱ, L′)-uniform graph with L′ = L\sqrt{n/|A|}.

The Ramanujan graphs X = X^{p,q} constructed in [16, 17] depend on primes p and q, which have to satisfy certain simple arithmetical conditions. These graphs X^{p,q} are (p + 1)-regular and have n = q(q^{2} − 1)/2 vertices. We shall need to construct linear-sized (ϱ, O(1))-uniform graphs with m vertices and average degree around r, where m and r are integers, which we may suppose to be large. The following lemma asserts that this can be done efficiently.

Lemma 2.2. There exists a constant r_{1} such that for all r_{0} ≥ r_{1} there is an m_{1} = m_{1}(r_{0}) such that the following holds. Let m ≥ m_{1} be given. Then we may explicitly construct an adjacency list representation of a particular (ϱ, 5)-uniform graph J on V (J) = {1, …, m} with average degree r = ϱm satisfying r_{0} ≤ r ≤ 2r_{0} in time O(m(log m)^{O(1)}).

To construct the graph J as in Lemma 2.2, one first finds suitable primes p and q so that n = q(q^{2} − 1)/2 is only a little larger than m (the existence of such primes follows from Dirichlet’s theorem on primes in arithmetic progressions). We have plenty of time for finding these p and q. We now construct X^{p,q} and then take an arbitrary induced subgraph J ⊂ X^{p,q} on m vertices; the (ϱ, 5)-uniformity of J follows from Lemma 2.1. We omit the details.

Notation. We use the following non-standard notation: we write O_{1}(x) for any term y such that |y| ≤ x.

Lemma 2.3. Let η_{0} > 0 and L > 0 be given. Then there is an r_{0} = r_{0}(η_{0}, L) such that any m-vertex (ϱ, L)-uniform graph J with ϱm ≥ r_{0} has the following property: if X ⊂ V (J) is such that η = |X|/n ≥ η_{0}, then e(J[X]) = (1 + O_{1}(η_{0}))η^{2}e(J). Here, as usual, e(J) stands for the number of edges of the graph J.

2.2 The algorithm. Our algorithm A first preprocesses the input graph G and only then runs a more sophisticated procedure. We first describe the preprocessing stage quite informally and then proceed to describe the heart of Algorithm A in detail in §2.2.3.

However, we have to start with setting up some constants.

2.2.1 Definition of the constants. Algorithm A is given a constant 0 < ε < 1. We first let

ε_{0} = \frac{1}{2}ε, δ = \frac{1}{4}ε_{0}^{5}, and r_{A} = 1500ε_{0}^{−8}. (2.4)

Now we put

θ = \frac{1}{4}δ^{2}, ε′′ = min \{\frac{1}{25}θ, \frac{1}{20}ε^{3}, \frac{1}{15}ε_{0}^{5/2}\} , (2.5)

and ε′ = (ε′′)^{2} ≤ min \{\frac{1}{400}ε^{6}, \frac{1}{160}ε_{0}^{5}\} .

We also let

ε_{1} = min \{\frac{1}{32}δ^{2}ε^{6}, \frac{1}{10}ε^{3}θ\} and (2.6)

η_{0} = min \{\frac{1}{3}ε′′, \frac{1}{8}ε^{6}, \frac{1}{4}θ\} .

We set L = 5 and let r_{B} = r_{0}(η_{0}, L) be as given in Lemma 2.3. Finally, we let

r_{0} = max{r_{A}, r_{B}}. (2.7)

The reader may find it useful to keep in mind the following relationship among the constants:

(2.8) ε′ ≪ ε′′ ≪ ε,  η_{0} ≪ ε′′ ≪ θ ≪ δ,
and ε′ ≪ ε_{1} ≪ δ, ε, θ.

2.2.2 The preprocessing stage. We first observe that if the graph G = (V_{1}, V_{2}; E) is such that p(G) = d(V_{1}, V_{2}) = |E|/m^{2} ≤ ε^{3}, then G is ε-regular (we omit the proof of this standard observation). Therefore, we suppose that

p(G) > ε^{3}. (2.9)

We now observe that we may remove some vertices of our graph G so that we either obtain a subgraph H ⊂ G that is essentially degree-regular (all degrees are about the same), or else in the process of removing these vertices we locate a witness to the ε′-irregularity of G. This is formalized in the following lemma (a sketch of the proof is given in the appendix).

Lemma 2.4. Suppose G = (V_{1}, V_{2}; E) is a balanced bipartite graph with |V_{1}| = |V_{2}| = m, and suppose that (2.9) holds. There is a procedure that runs in time O(m^{2}) such that either (i) our procedure produces a bipartite subgraph H ⊂ G, say H = (U_{1}, U_{2}; F), such that (a) if m_{i} = |U_{i}| (i = 1, 2), then

(1 − 2ε′)m < m_{i} ≤ m, (2.10)

(b) if p(H) = |F |/m_{1}m_{2}, then

p(H) = p(G) + O_{1}(5ε′), (2.11)

and (c) for all u_{i} ∈ U_{i} (i = 1, 2), we have

d(u_{i}) = (p(H) + O_{1}(10ε′))m_{3−i}, (2.12)

where d(u_{i}) stands, as usual, for the degree of the vertex u_{i} in the graph H, or else (ii) our procedure produces a witness to the ε′-irregularity of G.

For convenience, we let Ξ(m, ε′) be the family of subgraphs H of G that satisfy (a)–(c) in (i) of Lemma 2.4 above.

2.2.3 The main procedure. In view of Lemma 2.4, we now suppose that we have a subgraph H = (U_{1}, U_{2}; F) ⊂ G with H ∈ Ξ(m, ε′). Our algorithm A now generates a (ϱ, L)-uniform graph J with vertex set U_{1} and with average degree r = ϱm_{1} satisfying (cf. Lemma 2.2)

r_{0} ≤ r ≤ 2r_{0} . (2.13)

We now introduce some notation. We say that property P(J, δ) holds if

∑_{{x,y}∈J} |d_{H}(x, y) − p(H)^{2}m_{2}| ≤ δe(J)p(H)^{2}m_{2}, (2.14)

where we write {x, y} ∈ J to mean that {x, y} is an edge of J, e(J) stands for the number of edges J, and p(H) = e(H)/|U_{1}||U_{2}| = |F |/m^{2}. Moreover, let us write J(u) (u ∈ U_{2}) for the graph J[N(u)] induced by the neighbourhood N(u) of u in H. We define a 0–1 matrix M = (M(e, u))_{e,u} indexed by E(J) × U_{2} as follows:

(2.15) M(e, u) = \begin{cases}1 & if e ∈ J(u) \\ 0 & otherwise. \end{cases}

Therefore, clearly, M(e, u) = 1 if and only if both endpoints of e are adjacent to u.

Algorithm A now proceeds as follows:

1. A verifies whether P(J, δ) holds; if it does, then A claims that G is ε-regular and halts.

2. If P(J, δ) does not hold, then A computes the matrix M = (M(e, u))_{e,u} defined above. Moreover, A finds and fixes a vertex u_{0} ∈ U_{2} for which we have

∑_{u′∈U_{2}} ∑_{e∈J(u_{0})} M(e, u′) ≥ (1 + \frac{δ^{2}}{2} ) p(H)^{4}m_{2}e(J). (2.16)

[The existence of such a vertex u_{0} is proved later.]

3. A now sets U = N(u_{0}) and sets

(2.17) W = W_{θ} = {u′ ∈ U_{2} : u′satisfies (2.18)}

where

∑_{e∈J(u_{0})} M(e, u′) ≥ (1 + θ)p(H)^{4}e(J). (2.18)

4. A outputs (U, W) and claims that this is a witness to the ε′-irregularity of G.

2.2.4 Correctness and analysis of Algorithm A. The correctness of A follows from Lemmas 2.5 and 2.6 below. The first lemma says that if Algorithm A claims that G is ε-regular in Step 1, then this is indeed the case.

Lemma 2.5. If property P(J, δ) holds, then G is εregular.

Lemma 2.6. If property P(J, δ) fails, then G is not ε′- regular, and the pair (U, W) produced by Algorithm A is indeed a witness for the ε′-irregularity of G.

We shall prove the two lemmas above in §3. The next simple lemma tells us that A has time complexity O(m^{2}).

Lemma 2.7. Algorithm A described in §2.2 runs in time O(m^{2}).

Proof. This is quite straightforward and we omit the proof. Let us only observe that the fact that J has O(m) edges is crucial, as it is this that allows us to check (2.14) in O(m^{2}) time.

3 Proofs of the Main Lemmas 3.1 Proof of Lemma 2.5. We say that the graph H has property Q(J, δ) if the following inequality holds true:

∑_{{x,y}∈J} |d(x, y) + p(H)^{2}m_{2} − (d(x) + d(y))p(H)|

≤ δp(H)^{2}m_{2}e(J). (3.19)

Claim 3.1. Let δ > 0 be fixed. If a graph H ∈ Ξ(m, ε′) has property P(J, δ), then it has property Q(J, 2δ).

The proof of Claim 3.1 is quite straightforward and can be found in the appendix. In view of the above claim, to prove Lemma 2.5 it is enough to show that Q(J, 2δ) implies the ε_{0}-regularity of H. Let A = (a_{k,l})_{k,l} be a matrix indexed by U_{1} × U_{2}, with entries

a_{k,l} = \begin{cases}−(1 − p) & if \{k, l\} ∈ E(H) \\ p & otherwise. \end{cases}

Moreover, for i ∈ U_{1}, let v_{i} = (a_{i,1}, …, a_{i,m_{2}}) be the ith row of A. Straightforward calculations show that ⟨v_{i}, v_{j}⟩ = d(i, j) + p(H)^{2}m_{2} − (d(i) + d(j))p(H), and hence the following claim follows easily from the definition of property Q (see (3.19)).

Claim 3.2. For every H ∈ Ξ(m, ε′) that has property Q(J, 2δ), the rows of A are such that

∑_{{i,j}∈J} |⟨v_{i}, v_{j}⟩| ≤ 2δp(H)^{2}m_{2}e(J). (3.20)

Let U ⊂ U_{1} and W ⊂ U_{2}. To shorten our notation ∑_{ij∈J}^{U} will denote summation over {i, j} ∈ E(J) such that i, j ∈ U. Furthermore, for i ∈ U let w_{i} be the restriction of the vector v_{i} to W, i.e., w_{i} = (a_{i,j})_{j∈W}. We clearly have ∑_{ij∈J}^{U} |⟨v_{i}, v_{j}⟩| ≤ ∑_{{i,j}∈J} |⟨v_{i}, v_{j}⟩|. We now compare ∑_{ij∈J}^{U}⟨v_{i}, v_{j}⟩ with ∑_{ij∈J}^{U}⟨w_{i}, w_{j}⟩. We have

∑_{ij∈J}^{U}⟨v_{i}, v_{j}⟩ = ∑_{ij∈J}^{U}⟨w_{i}, w_{j}⟩ + ∑_{k∉W} ∑_{ij∈J}^{U} a_{i,k}a_{j,k}. (3.21)

For k ∈ U_{2} we set S_{k}^{U} = ∑_{ij∈J}^{U} a_{i,k}a_{j,k}, and proceed to estimate this quantity. For k ∈ U_{2} let U^{+} ⊂ U be the set of non-neighbours of the vertex k in U and let U^{−} ⊂ U be the set of neighbours of the vertex k in U. Set α = |U^{−}| and β = |U^{+}|. Note |U| = α + β. Thus, using the definition of the matrix A, we can write

S_{k}^{U} = e_{J}(U^{−})(1 − p(H))^{2} + e_{J}(U^{+})p(H)^{2}
(3.22)  − e_{J}(U^{−}, U^{+})p(H)(1 − p(H)).

The (ϱ, L)-uniformity of J implies the following claim, whose proof is given in the appendix.

Claim 3.3. For all k ∈ W and U ⊂ U_{1}, we have

S_{k}^{U} = \frac{ϱ}{2}[α(1 − p(H)) − βp(H)]^{2} + O_{1}(3L\sqrt{r} · |U|) . (3.23)

Identity (3.21) and Claims 3.2 and 3.3 above imply an upper and a lower bound on ∑_{ij∈J}^{U}⟨w_{i}, w_{j}⟩ as follows (cf. appendix):

∑_{ij∈J}^{U}⟨w_{i}, w_{j}⟩ (3.24)

≤ 2δp(H)^{2}m_{2}e(J) + 3L\sqrt{r}|U|(m_{2} − |W |)

and

∑_{ij∈J}^{U}⟨w_{i}, w_{j}⟩ (3.25)

≥ \frac{ϱ}{2}|U|^{2}|W ||d(U, W) − p(H)|^{2} − 3L\sqrt{r}|U| |W |.

Now we are ready to show that H is ε_{0}-regular. Fix U ⊂ U_{1}, |U| ≥ ε_{0}|U_{1}| = ε_{0}m_{1}, and W ⊂ U_{2}, |W | ≥ ε_{0}|U_{2}| = ε_{0}m_{2}. Set u = |U| and w = |W |. Recall that d(U, W) stands for the Szemerédi density of the pair (U, W) and d(U_{1}, U_{2}) = p = p(H) in our notation. Combining the lower and upper bounds on

∑_{ij∈J}^{U}⟨w_{i}, w_{j}⟩ (cf. (3.24) and (3.25)), we infer
|d(U, W) − p(H)|^{2}

≤ \frac{2}{ϱu^{2}w} (2δp(H)^{2}m_{2}e(J) + 3L\sqrt{r} · um_{2})

≤ \frac{4δp(H)^{2}m_{2}}{ϱu^{2}w} × \frac{rm_{1}}{2} + \frac{6L\sqrt{r} · um_{2}}{ϱu^{2}w}

≤ \frac{2δp(H)^{2}m_{1}^{2}m_{2}}{u^{2}w} + \frac{6Lm_{2}\sqrt{r}}{ϱuw}

≤ \frac{2δp(H)^{2}}{ε_{0}^{3}} + \frac{6L}{\sqrt{r} · ε_{0}^{2}}

≤ \frac{ε_{0}^{2}}{2} + \frac{ε_{0}^{2}}{2} = ε_{0}^{2}.

The last inequality follows because of our choice of δ and r ≥ r_{0} ≥ r_{A}.

Finally, we observe that the ε_{0}-regularity of H = (U_{1}, U_{2}; F) implies the ε-regularity of G = (V_{1}, V_{2}; F). This follows because ε′ ≪ ε_{0} < ε. We omit the details.

3.2 Proof of Lemma 2.6. For this proof, the reader may find it convenient to recall the hierarchy of the constants given in (2.8). Recall we have constants δ and ε with 0 < δ ≪ ε. We also have

p = p(H) ≥ \frac{1}{2}ε^{3}. (3.26)

Note that (3.26) is guaranteed to hold for the graph H that we obtain after preprocessing H as described in §2.2.

Suppose that property P(J, δ) fails for H. Thus

∑_{{x,y}∈J} |d(x, y) − p^{2}m_{2}| > δe(J)p^{2}m_{2}. (3.27)

A short calculation (see appendix) shows that we can write

∑_{{x,y}∈J} (d(x, y) − p^{2}m_{2})^{2} (3.28)

= ∑_{{x,y}∈J} d(x, y)^{2} − (1 + O_{1}(6ε′′))p^{4}m_{2}^{2}e(J).

Applying the Cauchy–Schwarz inequality to the lefthand side of (3.28) and using (3.27) we get

∑_{{x,y}∈J} (d(x, y) − p^{2}m_{2})^{2} (3.29)

≥ \frac{1}{e(J)}( ∑_{\{x,y\}∈J} |d(x, y) − p^{2}m_{2}|)^{2}

> δ^{2}p^{4}m_{2}^{2}e(J).

Comparing (3.28) and (3.29), and recalling (2.5), we deduce that

∑_{\{x,y\}∈J} d(x, y)^{2} ≥ (1 + \frac{δ^{2}}{2} ) p^{4}m_{2}^{2}e(J) . (3.30)

The following claim evaluates the sum on the left-hand side of (3.30) in terms of the matrix M = (M(e, u))_{e,u} defined in §2.2.

Claim 3.4.

∑_{{x,y}∈J} d(x, y)^{2} = ∑_{u∈U_{2}} ∑_{u′∈U_{2}} ∑_{e∈J(u)} M(e, u′). (3.31)

The proof of (3.31) is included in the appendix. Combining (3.30) and (3.31), we infer that there is a vertex u_{0} ∈ U_{2} for which we have

∑_{u′∈U_{2}} ∑_{e∈J(u_{0})} M(e, u′) ≥ (1 + \frac{δ^{2}}{2} ) p^{4}m_{2}e(J). (3.32)

Following the algorithm, we let such a vertex u_{0} be fixed. As in the algorithm, we now put U = N(u_{0}) and consider

W = W_{θ} = {u′ ∈ U_{2} : ∑_{e∈J(u_{0})} M(e, u′) ≥ (1 + θ)p^{4}e(J)} . (3.33)

One may prove that both U and W are large sets (the proof is given in the appendix).

Claim 3.5. We have |U| ≥ ε_{1}m_{1} and |W | ≥ ε_{1}m_{2}.

Before we proceed, we observe, using the definition of matrix M, that for all u′ ∈ U_{2} we have

∑_{e∈J(u_{0})} M(e, u′) = e(J[N(u_{0}) ∩ N(u′)]). (3.34)

We now infer a lower bound for the codegree d(u_{0}, u′) for the case in which u′ ∈ W using (3.34) and the fact that the edges of J are extremely well distributed.

Claim 3.6. For all w ∈ W, we have d(u_{0}, w) ≥ (1 + θ/3) p^{2}m_{1}.

See the appendix for the proof of Claim 3.6. It follows immediately from Claim 3.6 that e(U, W) ≥ (1 + \frac{θ}{3}) p^{2}m_{1}|W |, which implies

d(U, W) = \frac{e(U, W)}{|U||W |} ≥ \frac{(1 + θ/3)p^{2}m_{1}|W |}{(1 + ε′′)pm_{1}|W |}

(3.35)  ≥ (1 + \frac{θ}{4}) p > p + ε_{1}.

Since we have already proved that |U| ≥ ε_{1}m_{1} and |W | ≥ ε_{1}m_{2} (see Claim 3.5), inequality (3.35) tells us that (U, W) is a witness to the ε_{1}-irregularity of H. We shall now prove that (U, W) is in fact a witness

to the ε′-irregularity of G. We have

|U| ≥ ε_{1}m_{1} ≥ ε_{1}(1 − 2ε′)m ≥ ε′m (3.36)

and

|W | ≥ ε_{1}m_{2} ≥ ε_{1}(1 − 2ε′)m ≥ ε′m . (3.37)

Because of (2.11) and (3.35), we have

d(U, W) > p + ε_{1} ≥ p(G) − 5ε′ + ε_{1} ≥ p(G) + ε′. (3.38)

In view of (3.36), inequality (3.38) tells us that (U, W) is indeed a witness to the ε′-irregularity of G, as required.

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] 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), no. 1, pp. 80– 109.

[3] N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy, 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.

[4] N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy, Efficient testing of large graphs, Combinatorica 20 (2000), no. 4, pp. 451–476.

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

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

[7] D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput. 9 (1990), no. 3, pp. 251–280.

[8] 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, pp. 598–620.

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

[10] A. Frieze and R. Kannan, Quick approximation to matrices and applications, Combinatorica 19 (1999), no. 2, pp. 175–220.

[11] A. Frieze and R. Kannan, A simple algorithm for constructing Szemerédi’s regularity partition, Electronic Journal of Combinatorics 6 (1999), no. 1, Research Paper 17, 7 pp. (electronic).

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

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

[14] O. Goldreich, S. Goldwasser, and D. Ron, Property testing and its connection to learning and approximation, Journal of the Association for Computing Machinery 45 (1998), no. 4, pp. 653–750.

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

[16] A. Lubotzky, R. Phillips, and P. Sarnak, Explicit expanders and the Ramanujan conjectures, Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (STOC ’86) (Berkeley, California), ACM, 1986, pp. 240–246.

[17] A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), pp. 261–277.

[18] E. Szemerédi, 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.

Appendix: Some proofs We summarize all the postponed proofs and calculations in this appendix.

Proof of Lemma 2.4. (Sketch) We first omit the vertices u in V_{2} for which the condition

d(u) = (p(G) + O_{1}(ε′))m (3.39)

fails. If the number of such vertices is ≥ 2ε′m, we may easily produce a witness to the ε′-irregularity of G as in (ii) in the statement of our lemma. Suppose therefore that the number of such vertices is < 2ε′m. Let U_{2} ⊂ V_{2} be the resulting subset of V_{2}, and let m_{2} = |V_{2}| > (1 − 2ε′)m. We now omit the vertices u ∈ V_{1} for which the condition

d(u) = (p(G) + O_{1}(ε′))m_{2} (3.40) fails. Again, if the number of such vertices is ≥ 2ε′m, we may easily produce a witness to the ε′-irregularity of G. If the number of such vertices is < 2ε′m, the resulting graph H is as in (i) in the statement of our lemma.

Deferred proofs for Lemma 2.5

Here we present the proofs of the claims and identities used in the proof of Lemma 2.5.

Proof of Claim 3.1. Let H satisfy P(J, δ) and H ∈ Ξ(m, ε′). We have

(3.41) ∑_{{x,y}∈J} |d(x, y) + p(H)^{2}m_{2} − (d(x) + d(y))p(H)|

≤ ∑_{{x,y}∈J} |d(x, y) − p(H)^{2}m_{2}|

+ 2p(H) ∑_{x∈U_{1}} |p(H)m_{2} − d(x)|d_{J}(x)

≤ 2δp(H)^{2}m_{2}e(J)

since ε′ ≤ δ/40 (see (2.5)).

Proof of Claim 3.3. Recall that for two numbers a, b we write a = O_{1}(b) if and only if |a| ≤ b.

Since J is a (ϱ, L)-uniform graph, we get

e_{J}(U^{−}) = ϱ\binom{|U^{−}|}{2} + O_{1} (2L\sqrt{r} · |U^{−}|)

= ϱ\binom{α}{2} + O_{1} (2L\sqrt{r} · α)

= \frac{ϱα^{2}}{2} − \frac{ϱα}{2} + O_{1} (2L\sqrt{r} · α)
e_{J}(U^{+}) = \frac{ϱβ^{2}}{2} − \frac{ϱβ}{2} + O_{1} (2L\sqrt{r} · β)
e_{J}(U^{−}, U^{+}) = ϱαβ + O_{1} (L\sqrt{rαβ}) .

To bound S_{k}^{U} we are going to use the inequalities α(1 − p(H))^{2} + βp(H)^{2} ≤ α + β and 2(α + β) + \sqrt{αβ} ≤ \frac{5}{2}(α + β). We get for the upper bound on S_{k}^{U}

S_{k}^{U} − \frac{1}{2}ϱ [α(1 − p(H)) − βp(H)]^{2}

≤ −ϱ\frac{α}{2}(1 − p(H))^{2} − ϱ\frac{β}{2} p(H)^{2}

+2L\sqrt{r} · α(1 − p(H))^{2} + 2L\sqrt{r} · βp(H)^{2}

+L\sqrt{r} · \sqrt{αβ} · p(H)(1 − p(H))

≤ 2L\sqrt{r}(α + β) + L\sqrt{r} · \sqrt{αβ} ≤ 3L\sqrt{r}(α + β) = 3L\sqrt{r} · |U| .

We note that we got a bound linear in |U| since L and r are constants.

Similarly, we get for the lower bound

S_{k}^{U} − \frac{1}{2}ϱ [α(1 − p(H)) − βp(H)]^{2}

≥ −ϱ\frac{α}{2}(1 − p(H))^{2} − ϱ\frac{β}{2} p^{2}

−2L\sqrt{r} · α(1 − p(H))^{2} − 2L\sqrt{r} · βp(H)^{2}

−L\sqrt{r} · \sqrt{αβ} · p(H)(1 − p(H))

≥ −ϱ\frac{α}{2}(α + β) − 2L\sqrt{r} · (α + β) − L\sqrt{r} · \sqrt{αβ}

≥ −\frac{ϱ}{2}(α + β) − L\sqrt{r} · \frac{5}{2}(α + β)

≥ −\frac{1}{2}|U| (\frac{r}{m} + 5L\sqrt{r})

≥ −3L\sqrt{r} · |U| .

Derivation of the upper and lower bounds (3.24) and (3.25) on ∑_{ij∈J}^{U}⟨w_{i}, w_{j}⟩. To derive an upper bound on ∑_{ij∈J}^{U}⟨w_{i}, w_{j}⟩ we use (3.21). We get

∑_{ij∈J}^{U}⟨w_{i}, w_{j}⟩ = ∑_{ij∈J}^{U}⟨v_{i}, v_{j}⟩ − ∑_{k∉W} S_{k}^{U}.

Note that (3.23) implies S_{k}^{U} ≥ −3L\sqrt{r}|U|. Thus Claim 3.2 and this lower bound on S_{k}^{U} imply

∑_{ij∈J}^{U}⟨w_{i}, w_{j}⟩ ≤ 2δp(H)^{2}m_{2}e(J)
+3L\sqrt{r}|U|(m_{2} − |W |).

To estimate ∑_{ij∈J}^{U}⟨w_{i}, w_{j}⟩ from below, we first write

∑_{ij∈J}^{U}⟨w_{i}, w_{j}⟩ = ∑_{k∈W} ∑_{ij∈J}^{U} a_{i,k}a_{j,k} = ∑_{k∈W} S_{k}^{U}.

Set u = |U|, w = |W |, and write d_{U}(k) = |U^{−}| = α for the size of the intersection of the neighbourhood of the vertex k with the set U and β = |U \U^{−}| (as introduced in the main text). We have

∑_{ij∈J}^{U}⟨w_{i}, w_{j}⟩ = ∑_{k∈W} S_{k}^{U}

≥ ∑_{k∈W} (\frac{ϱ}{2}[α(1 − p(H)) − βp(H)]^{2} − 3L\sqrt{r} · u) ,

which, by Cauchy–Schwarz, is at least

\frac{ϱ}{2w} [ ∑_{k∈W}(α(1 − p(H)) − βp(H))]^{2} − 3L\sqrt{r}uw

≥ \frac{ϱ}{2w} [ ∑_{k∈W}(d_{U}(k) − up(H))]^{2} − 3L\sqrt{r} · uw

= \frac{ϱ}{2w} |e(U, W) − p(H)uw|^{2} − 3L\sqrt{r}uw

= \frac{ϱ}{2}u^{2}w|d(U, W) − p(H)|^{2} − 3L\sqrt{r} · uw.

Deferred proofs for Lemma 2.6

This section contains the proofs of the claims and identities used in the proof of Lemma 2.6.

Derivation of identity (3.28). Let us first observe that

(3.42) ∑_{{x,y}∈J} (d(x, y) − p^{2}m_{2})^{2}

= ∑_{{x,y}∈J} (d(x, y)^{2} − 2d(x, y)p^{2}m_{2} + p^{4}m_{2}^{2})

= ∑_{{x,y}∈J} d(x, y)^{2} −2p^{2}m_{2} ∑_{{x,y}∈J} d(x, y)+p^{4}m_{2}^{2}e(J).

However,

∑_{{x,y}∈J} d(x, y) = ∑_{{x,y}∈J} |N(x) ∩ N(y)|
= ∑_{u_{2}∈U_{2}} e(J[N(u_{2})])
= ∑_{u_{2}∈U_{2}}(1 + O_{1}(η_{0}))(1 + O_{1}(ε′′))^{2}p^{2}e(J),

where we used that |N(u_{2})| = d(u_{2}) = (p + O_{1}(10ε′))m_{1} = (1 + O_{1}(ε′′))pm_{1} ≥ η_{0}m_{1}. Therefore

∑_{{x,y}∈J} d(x, y) = (1 + O_{1}(3ε′′))p^{2}m_{2}e(J) . (3.43)

From (3.42) and (3.43) we obtain that

∑_{{x,y}∈J} (d(x, y) − p^{2}m_{2})^{2}

= ∑_{{x,y}∈J} d(x, y)^{2} − (1 + O_{1}(6ε′′))p^{4}m_{2}^{2}e(J) ,

as claimed in (3.28).

Proof of Claim 3.4. Clearly, if e = {x, y} ∈ J, then

d(x, y) = |N(x) ∩ N(y)| = ∑_{u∈U_{2}} M(e, u) , (3.44)

and hence

d(x, y)^{2} = ∑_{u∈U_{2}} ∑_{u′∈U_{2}} M(e, u)M(e, u′) . (3.45)

Therefore

∑_{{x,y}∈J} d(x, y)^{2} = ∑_{u∈U_{2}} ∑_{e∈J} M(e, u) ∑_{u′∈U_{2}} M(e, u′)
= ∑_{u∈U_{2}} ∑_{e∈J(u)} ∑_{u′∈U_{2}} M(e, u′)
= ∑_{u∈U_{2}} ∑_{u′∈U_{2}} ∑_{e∈J(u)} M(e, u′).

Proof of Claim 3.5. Using (2.12) we, clearly, have

|U| = (p + O_{1}(10ε′))m_{1} = (1 + O_{1}(ε′′))pm_{1} ≥ ε_{1}m_{1}. (3.46)

By the definition of W, we have

∑_{u′∈U_{2}} ∑_{e∈J(u_{0})} M(e, u′) (3.47)

< (1 + θ)p^{4}m_{2}e(J)
+|W |(1 + O_{1}(η_{0}))(p + O_{1}(10ε′))^{2}p^{2}e(J)

= (1 + θ)p^{4}m_{2}e(J) + (1 + O_{1}(3ε′′))|W |p^{4}e(J). Comparing (3.32) and (3.47), we obtain

2|W |p^{2}e(J) ≥ (1 + O_{1}(3ε′′))|W |p^{2}e(J) ≥ \frac{1}{4}δ^{2}p^{4}m_{2}e(J), (3.48)

and hence

|W | ≥ \frac{1}{8}δ^{2}p^{2}m_{2} ≥ \frac{1}{32}δ^{2}ε^{6}m_{2} ≥ ε_{1}m_{2}, (3.49)

as required. Proof of Claim 3.6. Suppose to the contrary that our claim fails. Then we have

e(J[N(u_{0}) ∩ N(w)]) < (1 + O_{1}(η_{0})) (1 + \frac{θ}{3})^{2} p^{6}e(J) (3.50)

if d(u_{0}, w) ≥ η_{0}m_{1}, and we have e(J[N(u_{0}) ∩ N(w)]) < 2η_{0}^{2}e(J) (3.51) if d(u_{0}, w) < η_{0}m_{1}. In either case, we have e(J[N(u_{0}) ∩ N(w)]) < (1 + θ)p^{6}e(J) . (3.52) However, in view of the definition of W (see (3.33)) and (3.34), inequality (3.52) cannot hold. This contradiction shows that our claim must indeed hold.