AN OPTIMAL ALGORITHM FOR CHECKING REGULARITY ^{∗}

Y. KOHAYAKAWA^{†}, V. RÖDL^{‡}, AND 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 [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]. 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 [N. Alon, R. A. Duke, H. Lefmann, V. Rödl, and R. Yuster, The algorithmic aspects of the regularity lemma, Journal of Algorithms, 16(1) (1994), pp. 80–109], 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.

Key words. Szemerédi’s regularity lemma, quasi-randomness, deterministic sampling, expander graphs, regular pairs

AMS subject classifications. 05C35, 05C85, 05C99, 68R10

1. Introduction and the main result. Szemerédi’s regularity lemma [31] is a fundamental result in graph theory (see [25] 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 [11]) is the time required to square a 0–1 matrix over the integers. More recently, Frieze and Kannan [18] (see also [19]) showed that sampling can 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 paper, we present a deterministic algorithm that solves this problem in O(m^{2}) time. Given our algorithm, one can derive in a standard way an algorithm for Szemerédi’s regularity lemma that finds a regular partition of an n-

∗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 (Proc. 96/04505–2). The second author was partially supported by NSF Grant 0071261. The third author was partially supported by NSF grant DMS–0301228. The collaboration of these authors is supported by a CNPq/NSF INT–0072064 cooperative grant. Some of the results in this paper appeared in an extended abstract in the proceedings of SODA 2002.

†Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508– 090 São Paulo, SP, 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).

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 = (A, B; E) be a bipartite graph. If ∅ ≠ U ⊂ A, ∅ ≠ V ⊂ B, the density of (U, V) in G is d(U, V) = e(U, V)/|U||V |, where we write e(U, V) = e_{G}(U, V) for the number of edges with one endpoint in U and the other endpoint in V. For ε > 0, we say that G is ε-regular if, for all U ⊂ A, |U| ≥ ε|A|, and V ⊂ B, |V | ≥ ε|B|, we have

|d(U, V) − d(A, B)| ≤ ε . (1.1)

In case G is not ε-regular and a certain pair (U, V) certifies this fact, then we say that (U, V) is a witness to the ε-irregularity of G.

Let Γ = (V, E) be a graph. A partition (V_{i})_{i=0}^{k} of the vertex set V, V = ⋃_{i=0}^{k} V_{i}, is said to be an equitable partition (with the exceptional class V_{0}) if |V_{1}| = ⋯ = |V_{k}|. If V = ⋃_{i=0}^{k} V_{i} is an equitable partition of V such that the size of the exceptional class |V_{0}| ≤ εn and at least (1 − ε)\binom{k}{2} pairs (V_{i}, V_{j}), where 1 ≤ i < j ≤ k, are ε-regular, we say that the partition (V_{i})_{i=0}^{k} is an ε-regular partition. 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}).

Alon, Duke, Lefmann, Rödl, and Yuster [1, 2] proved the following algorithmic version of Theorem 1.1.

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 1.3. Given a graph G, a pair (U, W) of non-empty, 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 [15] suffices.

Theorem 1.4. There exists an algorithm A_{1} for which the following holds. When A_{1} receives as input an ε > 0 and a bipartite graph G = (A, B; E) with |A| = |B| = 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 [20] for a somewhat different approach to verifying regularity, based on singular values of matrices.) Our main result is an improvement of Theorem 1.4 above, and may be stated as follows.

Theorem 1.5 (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 = (A, B; E) with |A| = |B| = 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}/10^{24}. The running time of A is O(m^{2}).

We describe our algorithm A in §3.1. Deriving an algorithm for the regularity lemma from Theorem 1.5 is standard (cf. §3.2).

Corollary 1.6. 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.6, one obtains algorithms with optimal time complexity O(n^{2}). We also observe that a similar improvement may be obtained from Theorem 1.5 for the subgraph counting algorithm given in Duke, Lefmann, and Rödl [15].

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., [21] and [22, 23]). 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.4. Again, an O(n^{2}) time algorithm follows immediately from Theorem 1.5.

Finally, we mention that one may prove a ‘non-bipartite version’ of Theorem 1.5. 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 [10]. Moreover, if Γ is not quasi-random, then our algorithm will produce a suitable witness proving this, i.e., an induced subgraph with Ω(n) vertices whose density deviates substantially from the density of Γ (see Section 1.3.5 for more details).

1.2. Local conditions for regularity. One may prove Theorem 1.4 by considering a certain ‘local condition’ on G = (A, B; E) 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∈A} |d_{G}(x, y) − p(G)^{2}m| ≤ δp(G)^{2}m^{3}, (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|/|A||B| = |E|/m^{2}, with m = |A| = |B|, 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 in the same deterministic time. Some of the ideas described in this paragraph have appeared in the literature under many guises. (For a detailed discussion on the combinatorial aspects, see [24]; for applications of these ideas in theoretical computer science, see [28] and the references therein.) Basically, we are obtaining a somewhat surprising amount of information from ‘pairwise independence’. We do not go into the details here.

The key idea in the proof of Theorem 1.5 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 linear-sized expander J (see the definition of property P(J, δ) in §3.1.2).

1.3. Algorithmic applications. As mentioned above, Algorithms A and A′_{0} immediately imply improvements on deterministic algorithms that are based on Szemerédi’s regularity lemma. Here we present a few typical examples of such algorithms. For more algorithmic applications of the regularity lemma see [2] and [15].

1.3.1. MAXCUT in dense graphs. There has been considerable interest in the following computational problem recently.

Problem 1.7 (MAXCUT). Given a graph G, find a partition (U, W) of the vertex set of G so that the number of edges e(U, W) between U and W is maximum.

It follows from the algorithmic version of the regularity lemma that one may design a polynomial time approximation scheme for MAXCUT if the input graphs G are restricted to dense graphs. Let us be more precise.

Let α be a fixed positive real. In this section, we only consider graphs G with edge density e(G)\binom{|V (G)|}{2}^{−1} ≥ α. Theorem 1.2 implies the following result: for any ε and α > 0, there exist a constant C(ε, α) and a deterministic algorithm A_{MC} so that, given an n-vertex graph G with edge density ≥ α, algorithm A_{MC} returns a solution (U′, W′) for MAXCUT such that

e(U′, W′) ≥ (1 − ε)e(U^{∗}, W^{∗}), (1.3)

where (U^{∗}, W^{∗}) is an optimal solution for G. Furthermore, the running time of A_{MC} is ≤ C(ε, α)M(n).

Algorithm A_{MC} uses Algorithm A_{0} in Theorem 1.2 as a subroutine; we may use, instead, Algorithm A′_{0} in Corollary 1.6: let A′_{MC} be the corresponding algorithm.

Theorem 1.8. On input G as above, the deterministic algorithm A′_{MC} produces a partition (U, W) satisfying (1.3) in time ≤ C′(ε, α)n^{2}, where C′(ε, α) is a constant that depends only on ε and α.

We remark that a randomized algorithm with time complexity O(n^{2}) was already given by de la Vega [14]. For related results concerning randomized algorithms, the reader is referred to Frieze and Kannan [18, 19].

1.3.2. The quasi-Ramsey number and maximum acyclic subgraphs. Let f : E(K_{n}) → \{−1, 1\} be a function and set f(S) = ∑_{e∈\binom{S}{2}} f(e) where S ⊆ [n]. Here,

as usual, K_{n} stands for the complete graph on n vertices and \binom{S}{2} denotes the set of all pairs on the set S.

The quasi-Ramsey number g(n) is defined as

g(n) = min_{f} max_{S⊆[n]} |f(S)| .

Erdős and Spencer [17] showed that

c_{1}n^{3/2} ≤ g(n) ≤ c_{2}n^{3/2},

for some absolute constants c_{1} and c_{2} > 0.

Let T_{n} be a tournament and P_{n} a transitive tournament both on n vertices. Set |T_{n} ∩ P_{n}| to be the number of common oriented arcs of T_{n} and P_{n}. The tournament ranking function h(n) is defined by

h(n) = min_{T_{n}} max_{P_{n}} |T_{n} ∩ P_{n}| ,

i.e., h(n) is the maximum number of edges one can choose in any tournament of order n without creating an oriented cycle. Spencer [29, 30] showed that

c_{1}n^{3/2} ≤ h(n) − \frac{1}{2}\binom{n}{2} ≤ c_{2}n^{3/2},

for some absolute constants c_{1} and c_{2} > 0.

A polynomial time approximation scheme (PTAS) for a maximization problem is a family of algorithms {S_{ϱ}: 0 < ϱ < 1} as follows. For any given 0 < ϱ < 1, algorithm S_{ϱ} runs in polynomial time and finds a solution whose value is at least (1 − ϱ) OPT, where OPT in the optimal value. Using a constructive version of the regularity lemma Czygrinow, Poljak, and Rödl [13, Theorem 3] designed a PTAS for the ‘dense’ quasi-Ramsey problem and for tournament ranking.

For f : E(K_{n}) → {−1, 1} set OPT(f) = max_{S⊆[n]} |f(S)|. Our algorithm for the regularity lemma implies an improvement on the time complexity of the PTAS designed in [13].

Theorem 1.9. Let c > 0 be fixed. For every 0 < ϱ < 1, there is a O(n^{2}) time algorithm that constructs a set S such that

|f(S)| ≥ (1 − ϱ) OPT(f),

for any instance f: E(K_{n}) → {−1, 1} with OPT(f) ≥ cn^{2}.

Now, let OPT(T_{n}) = max_{P_{n}} |T_{n} ∩ P_{n}| where T_{n} is a tournament. Algorithm A′_{0} in Corollary 1.6 improves the time complexity of the PTAS designed in [13] to O(n^{2}).

Theorem 1.10. Let 0 < ϱ < 1. Then there is a O(n^{2}) time algorithm that, given a tournament T_{n}, constructs an ordering σ of the vertices of T_{n} so that at least (1 − ϱ) OPT(T_{n}) arcs agree with σ.

1.3.3. Robustly high-chromatic graphs. Goldreich, Goldwasser, and Ron [22, 23] have recently initiated a systematic study of property testing for combinatorial structures. Roughly speaking, in property testing, one has a property P of interest, and one is given an object X and a real number ε > 0. The task is then to decide whether X has P or it is ε-far from any object Y having P (we suppose our objects are in some metric space). Furthermore, we wish to perform this test extremely quickly; typically, the tests examine a small random portion of X and distinguish between the two cases above with high probability of success. Thus, in an appropriate computational model, the tests have sublinear complexity (see [22, 23] for details).

A graph property P that has been proved to be testable [22, 23] is the property of having chromatic number at least k, for any fixed k. This result was in fact implicit in [16], where the regularity lemma is used to prove that ‘robustly highchromatic graphs’ admit witnesses of bounded size. Indeed, the existential result in Theorem 1.11 below was proved in [16]. The algorithmic result in Theorem 1.11, but with time complexity O(M(n)), was proved in [1, 2].

Theorem 1.11. Let k ≥ 3 be an integer and let ε > 0 be a real constant. Then there exist integers n_{0} = n_{0}(k, ε) and f = f(k, ε) and a constant ν = ν(k, ε) > 0 such that if G = (V, E) is a graph with n ≥ n_{0} vertices, then either

(i) there exists a graph H on h ≤ f vertices with chromatic number χ(H) ≥ k that occurs in G at least νn^{h} times as a subgraph, or else

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

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

The approach in [22, 23] does not use the regularity lemma, and implies the existential part of Theorem 1.11. Moreover that approach also gives a randomized, polynomial time algorithm for the constructive part of Theorem 1.11.

Finally, we mention that Czumaj and Sohler [12] have recently proved that the property of having chromatic number at least k is also testable for hypergraphs.

1.3.4. Counting subgraphs. In this section, we describe an algorithm for approximately counting small subgraphs in large graphs. This algorithm will also be an application of Algorithm A′_{0} from Corollary 1.6.

We need to introduce some notation. We shall follow [15]. Let G = (V, E) be a 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}} 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, if w_{i} < w_{j}, then ϕ(w_{i}) < ϕ(w_{j}). Let H_{1}, …, H_{t}, where t = 2^{\binom{k}{2}}, be the list of all graphs on the set W and let σ_{k}(G) = (h_{1}, …, h_{t}) be the t-dimensional vector in which each 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 [15].

Theorem 1.12. Let k ≥ 3 be a fixed integer and suppose δ > 0 is a fixed real. There is an algorithm that, on input G, a labeled, ordered graph on n vertices, produces an approximation \overline{σ}_{k}(G) = (\overline{h}_{1}, …, \overline{h}_{t}) to the vector σ_{k}(G) = (h_{1}, …, h_{t}) with the property that

|h_{i} − \overline{h}_{i}| ≤ δ\binom{n}{k}

for all 1 ≤ i ≤ t. This algorithm runs in time O(n^{2}).

In [15], the authors consider the problem of approximating σ_{k}(G) for k = k(n) slowly increasing functions of n. Our results may be used to improve on the time complexity of the algorithms given in [15] for such k = k(n), but we shall not go into the details.

1.3.5. Checking quasi-randomness. Thomason [32] and Chung, Graham, and Wilson [10] initiated a systematic study of quasi-random properties of graphs: these are properties that are shared by almost all graphs, and are in fact deterministically asymptotically equivalent, i.e., if a large graph has one of these properties, then it in fact has all of them.

The investigation of quasi-randomness in combinatorics turned out to be a very rich line of research, as shows the series of papers by Chung and Graham on the subject (see [9] for recent developments, and the references therein). Besides graphs, other combinatorial structures such as tournaments, set-systems, and subsets of ℤ/nℤ, have been studied from this perspective (see [6, 7, 8].) Finally, we mention that applications of some of the underlying ideas in this area have occurred in the literature in different contexts; the interested reader is referred to [5, Chapter 9] and [24].

In this section, we shall consider the computational problem of determining whether or not a given graph is quasi-random. We are also interested in an additional requirement: in the case in which the input graph is not quasi-random, a ‘witness’ to certify this fact should be efficiently produced.

We shall use the following definition.

Definition 1.13. Let reals 0 < ε ≤ 1 and 0 < δ ≤ 1 be given. We shall say that a graph G is (1/2, ε, δ)-quasi-random if, for all U, W ⊂ V (G) with U ∩ W = ∅ and |U|, |W | ≥ δn, we have

|e_{G}(U, W) − \frac{1}{2}|U||W || ≤ \frac{1}{2}ε|U||W |.

In [24] the authors consider a new quasi-random property to develop an algorithm for testing quasi-randomness. Let G be a graph on n vertices and let J be a (ϱ, L)- uniform graph on the same vertex set (for the definition, see Section 2). To state the results we need to introduce some notation. For a vertex i of G we set N(i) to be its neighborhood. Further, we write N(i)△N(j) for the symmetric difference of the sets N(i) and N(j).

To decide about the quasi-randomness of G we introduce the following couple of properties. Let 0 < ε, δ ≤ 1 be real numbers. We say that G satisfies property T_{△}(J, ε) if we have

∑_{\{i,j\}∈E(J)}||N(i)△N(j)| − \frac{1}{2}n| ≤ \frac{1}{2}εne(J) .

Note that this property is closely related to our property P introduced below. Similarly, we say that G satisfies property T′_{△}(J, γ, ε) if the inequality

||N(i)△N(j)| − \frac{1}{2}n| ≤ \frac{1}{2}εn

fails for at most γe(J) edges {i, j} ∈ E(J).

The following two characterization theorems are proved in [24, Theorems 56, 57]. Theorem 1.14. For any 0 < ε, δ ≤ 1 and any L, there exist ε_{0} = ε_{0}(ε, δ, L) > 0

and r_{0} = r_{0}(ε, δ, L) ≥ 1 for which the following holds. Let G and J be two graphs on the same vertex set of n vertices. Assume further that J is a (ϱ, L)-uniform graph with the average degree r = ϱn ≥ r_{0}. Then, if G satisfies the property T_{△}(J, ε′) for some 0 < ε′ ≤ ε_{0}, then G is (1/2, ε, δ)-quasi-random.

Theorem 1.15. For any 0 < γ, ε ≤ 1 and any L, there exist ε_{1} = ε_{1}(γ, ε, L) > 0, δ_{1} = δ_{1}(γ, ε, L) > 0, r_{1} = r_{1}(γ, ε, L) ≥ 1, and N_{1} = N_{1}(γ, ε, L) ≥ 1, for which the following holds. Let G and J be two graphs on the same vertex set of n ≥ N_{1} vertices. Assume further that J is a (ϱ, L)-uniform graph with the average degree r = ϱn ≥ r_{1}. Then, if G is (1/2, ε′, δ′)-quasi-random for some 0 < ε′ ≤ ε_{1} and 0 < δ′ ≤ δ_{1}, then property T′_{△}(J, γ, ε) holds for G.

It is straightforward to see that the properties T and T′ can be checked in O(n^{2}) deterministic time. Moreover, if a graph G does not satisfy property T′_{△}(J, γ, ε), then one can, using the ideas from our present paper, construct a witness for the non-quasi-randomness of G in O(n^{2}) time.

2. Preliminaries. In this section, we discuss some basic properties and the algorithmic construction of certain very well known random looking graphs.

2.1. (ϱ, L)-uniformity. 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) with U ∩ W = ∅, we have

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

where r = ϱm. The following lemma is immediate.

Lemma 2.1. Let R = (V, E) be a (ϱ, L)-uniform, m-vertex graph and let ∅ ≠ A ⊂ V be given. Put J = R[A]. Then J is an (ϱ, L′)-uniform graph with L′ = L\sqrt{m/|A|}.

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

We shall need estimates on the number of edges induced on subsets of (ϱ, L)- uniform graphs. Below, if Γ is a graph, we write e(Γ) for the number of edges in Γ.

Lemma 2.3. Let J = (V, E) be a (ϱ, L)-uniform graph and let S ⊆ V be a nonempty subset of vertices of J. Then

e(J[S]) = ϱ\binom{|S|}{2} + O_{1}(Lr^{1/2}(|S| + 1))
(2.2)  = ϱ\frac{|S|^{2}}{2} + O_{1}(2Lr^{1/2}|S|),

where r = ϱ|V |.

Proof. Put s = |S|. Note that, for any 1 ≤ t < s, we have 2e(S)\binom{s−2}{t−1} = ∑_{T} e(T, S \ T), where the sum is extended over all T ⊂ S with |T | = t. Thus

e(S) = \frac{1}{2}\binom{s}{t}\binom{s − 2}{t − 1}^{−1} \{ϱ|T ||S \ T | + O_{1}(L\{rt(s − t)\}^{1/2})\}

for any 1 ≤ t < s. We use this relation with t = ⌊s/2⌋. Note that

\binom{s}{⌊s/2⌋}\binom{s − 2}{⌊s/2⌋ − 1}^{−1} = \frac{s(s − 1)}{⌊s/2⌋⌈s/2⌉} ≤ 4,

and so

e(S) = ϱ\binom{s}{2} + O_{1}(2L\{r⌊s/2⌋⌈s/2⌉\}^{1/2}) = ϱ\binom{s}{2} + O_{1}(Lr^{1/2}(s + 1)),

and the result follows.

In what follows, the following simple consequences of Lemma 2.3 will be useful. Lemma 2.4. Let η > 0 and L > 0 be given. Then there is an \overline{r} = \overline{r}(η, L) such

that any m-vertex (ϱ, L)-uniform graph J with ϱm ≥ \overline{r} has the two properties below. (a) If S ⊂ V (J) is such that |S| = νm ≥ ηm, then

e(J[S]) = (1 + O_{1}(η))ν^{2}e(J) . (2.3)
(b) If S ⊂ V (J) is such that |S| < ηm, then
e(J[S]) < 2η^{2}e(J) . (2.4)

2.2. Auxiliary results on expander graphs. The celebrated Ramanujan graphs of Lubotzky, Phillips, and Sarnak [26, 27] are explicitly constructible examples of linear-sized (ϱ, 2)-uniform graphs. We shall make crucial use of their construction.

The Ramanujan graphs X^{p,q} constructed in [26, 27] depend on certain primes p and q, which have to satisfy certain simple arithmetical conditions. The graphs X^{p,q} that we shall be interested in are (p+1)-regular and have q(q^{2}−1)/2 vertices. However, we shall need to construct linear-sized (ϱ, O(1))-uniform graphs with m vertices and average degree around r, where m and r are arbitrary integers (which we may assume to be large). The main result of this section, Lemma 2.5 below, asserts that this can be done efficiently. As the reader will see, we shall simply check that, given m and r, we may find suitable primes p and q so that an induced subgraph of X^{p,q} will do.

Lemma 2.5. There exists an Algorithm E satisfying the following properties. There is an absolute constant r_{1} such that for all r_{0} ≥ r_{1} there are constants m_{0} = m_{0}(r_{0}) and C_{0} = C_{0}(r_{0}) for which the following holds. Algorithm E receives as input integers r_{0} ≥ r_{1} and m ≥ m_{0} = m_{0}(r_{0}), and returns an adjacency list representation of a particular (ϱ, 3)-uniform graph J on m vertices with r = ϱm satisfying r_{0} ≤ r ≤ 2r_{0}. Furthermore, Algorithm E runs in time ≤ C_{0}m(log m)^{2}.

In the remainder of this section, we prove Lemma 2.5 above for completeness.

2.2.1. Ramanujan graphs. Before we start with the proof of Lemma 2.5, we recall the construction of Lubotzky, Phillips, and Sarnak [26, 27].

As usual, in what follows, if a is an integer and p is a prime with a not divisible by p, the Legendre symbol (\frac{a}{p}) is defined as 1 if a is a quadratic residue modulo p and as −1 if a is a quadratic non-residue modulo p. To describe the construction in [26, 27], let p and q be two unequal primes satisfying

p, q ≡ 1 (mod 4), (2.5)

and

(\frac{p}{q}) = 1. (2.6)

We now let S and T be the following sets. Below, i is an arbitrary fixed integer such that i^{2} ≡ −1 (mod q). We let

S = {(α_{0}, α_{1}, α_{2}, α_{3}) ∈ ℤ^{4} : α_{0}^{2} + α_{1}^{2} + α_{2}^{2} + α_{3}^{2} = p
with α_{0} > 0, odd, and α_{1}, α_{2}, α_{3} even}
(2.7)  T = \{ (\begin{matrix}α_{0} + iα_{1} & α_{2} + iα_{3} \\ −α_{2} + iα_{3} & α_{0} − iα_{1} \end{matrix}) : (α_{0}, α_{1}, α_{2}, α_{3}) ∈ S\} .

We now consider PSL(2, ℤ/qℤ) (the projective special linear group), which consists of the 2 × 2 matrices over ℤ/qℤ whose determinants are non-zero quadratic residues mod p, quotiented out by the equivalence relation that makes two such matrices equivalent if one is a non-zero scalar multiple of the other.

It will be convenient to observe that each element of PSL(2, ℤ/qℤ) (i.e., each equivalence class) may be represented by a matrix whose second row is either (0, 1), or else the second row is (1, x), where x is some arbitrary element of ℤ/qℤ. The existence of this simple ‘canonical representation’ for the elements of PSL(2, ℤ/qℤ) will be helpful below.

Observe that, if we consider the entries of the matrices in T modulo q, we get 2 × 2 matrices over ℤ/qℤ, with determinant p (mod q), which is a non-zero quadratic residue modulo q (cf. (2.6)). By a well known result of Jacobi and some simple arguments, one may check that there are p + 1 elements in T and that they are all distinct in PSL(2, ℤ/qℤ).

The graph X^{p,q} constructed in [26, 27] is the Cayley graph of PSL(2, ℤ/qℤ) relative to the set T. The vertices of X^{p,q} are the elements of PSL(2, ℤ/qℤ) and the edge set of X^{p,q} is so that {x, y} is an edge of X^{p,q} if and only if there is a t ∈ T such that x = ty (one may check that this is a symmetric relation). A key result concerning the graphs X^{p,q} is the following.

Theorem 2.6. The graph X^{p,q} is a non-bipartite (p + 1)-regular graph on n = q(q^{2} − 1)/2 vertices. Moreover, if the eigenvalues of X^{p,q} are |λ_{1}| ≥ ⋯ ≥ |λ_{n}|, then λ_{1} = p + 1 and

|λ_{j}| ≤ 2\sqrt{p} for all j > 1. (2.8)

Because of (2.8), the graphs X^{p,q} are called Ramanujan graphs. We now state the following well known pseudorandom property of the graphs X^{p,q}, which follows from (2.8) (see, e.g., Corollary 9.2.5 in [5]).

Corollary 2.7. The graph X^{p,q} is (ϱ, 2)-uniform, where ϱ = (p + 1)/n.

Having covered the basics of the Lubotzky, Phillips, and Sarnak construction, we turn to the proof of Lemma 2.5.

2.2.2. Proof of Lemma 2.5. We start with a simple lemma asserting the existence of appropriate primes p and q.

Lemma 2.8. There exists an absolute constant r_{1} such that, for any r_{0} ≥ r_{1}, there exists an integer m_{0} = m_{0}(r_{0}) for which the following holds. There is an Algorithm P that, on input (r_{0}, m), where r_{0} ≥ r_{1} and m ≥ m_{0} = m_{0}(r_{0}), produces a pair of primes p and q which satisfy

p ≠ q, p, q ≡ 1 (mod 4), and (\frac{p}{q}) = 1, (2.9)

1.4r_{0} ≤ p + 1 ≤ 2r_{0}, (2.10)

and

\sqrt[3]{2.1m} ≤ q ≤ 1.1\sqrt[3]{2.1m}. (2.11)

Algorithm P runs in time ≤ C_{1}m^{1/2}(log m)^{2}, where C_{1} = C_{1}(r_{0}) depends only on r_{0}.

Proof. Let us start recalling Dirichlet’s theorem on primes in arithmetic progressions. In particular, the quantitative version of Dirichlet’s theorem implies that for integers a and b with (a, b) = 1, there is an integer t_{a,b} such that for all t ≥ t_{a,b} there is a prime p ≡ a (mod b) in the interval [t, 11t/10] = {x: t ≤ x ≤ 11t/10}.

We let r_{1} = t_{1,8} + 1 and proceed to show that this choice of r_{1} will do. Thus, let an arbitrary integer r_{0} ≥ r_{1} be given, and let us define m_{0} = m_{0}(r_{0}) as required in our lemma. To that end, first observe that, by the choice of r_{1}, there is a prime p ≡ 1 (mod 8) satisfying (2.10). We fix such a prime p. Observe that we have p ≡ 1 (mod 4). Moreover, since p ≡ 1 (mod 8), we have that

(2.12) 2 is a quadratic residue modulo p.

Since (4, p) = 1, by the Chinese remainder theorem, there is a unique integer s with 1 ≤ s ≤ 4p satisfying

(2.13)  s ≡ 2 (mod p)  and  s ≡ 1 (mod 4).

We are finally ready to define m_{0} = m_{0}(r_{0}). We let

m_{0} = m_{0}(r_{0}) = max \{\frac{10}{21}t_{s,4p}^{3}, \frac{8}{2.1}r_{0}^{3}\} . (2.14)

Our aim now is to show that the choice for m_{0} = m_{0}(r_{0}) in (2.14) will do. Thus, let m ≥ m_{0}(r_{0}) be given. We shall now describe a procedure P to find the primes p and q as required. Our description will be quite informal.

The prime p with p ≡ 1 (mod 8) satisfying (2.10) may be found easily. We now need to determine a suitable value for q. We choose q among the integers in the arithmetic progression {4pk + s: k = 0, 1, 2, … }, where s is the integer satisfying 1 ≤ s ≤ 4p and (2.13). By Dirichlet’s theorem and our choice of m_{0} ≥ (10/21)t_{s,4p}^{3}, there is a prime q ≡ s (mod 4p) satisfying (2.11). We claim that our choice of s implies all properties promised for q. Indeed, q ≡ s ≡ 1 (mod 4). Furthermore, the quadratic reciprocity law implies (\frac{p}{q}) = (\frac{q}{p}), since both p, q ≡ 1 (mod 4). Using that q ≡ s ≡ 2 (mod p) and recalling (2.12), we have

(\frac{p}{q}) = (\frac{q}{p}) = (\frac{s}{p}) = (\frac{2}{p}) = 1.

Finally, note that m_{0} ≥ 8r_{0}^{3}/2.1 guarantees q > p and consequently condition (2.9) is satisfied. Therefore, the primes p and q as required do exist.

Let us now consider the time complexity of our procedure P above. We first observe that the search for p < 2r_{0} takes a quantity of steps that depends only on r_{0}. To find q, we have enough time to check all integers in the interval [\sqrt[3]{2.1m}, 1.1\sqrt[3]{2.1m}]. Since this interval is of length O(m^{1/3}), this will take O(m^{1/3} · m^{1/6}(log m)^{2}) = O(m^{1/2}(log m)^{2}) steps. The (log m)^{2} term accounts for the time complexity of arithmetic operations with integers having O(log m) digits.

We now describe Algorithm E, the existence of which is asserted in Lemma 2.5. Consider the integer r_{1} and the function m_{0}(r_{0}) whose existences are guaranteed by Lemma 2.8. On input (r_{0}, m), where r_{0} ≥ r_{1} and m ≥ m_{0}(r_{0}), Algorithm E performs the following steps.

1. Run Algorithm P on input (r_{0}, m) to obtain primes p and q as in the statement of Lemma 2.8.

2. List all elements of PSL(2, ℤ/qℤ), i.e., the vertex set of X^{p,q}, by enumerating all the canonical representatives of the elements in PSL(2, ℤ/qℤ).

3. Find all solutions to α_{0}^{2} + α_{1}^{2} + α_{2}^{2} + α_{3}^{2} = p that belong to S and construct T (see (2.7)).

4. For each vertex x of X^{p,q}, construct its adjacency list.

5. Set J to be any induced subgraph of X^{p,q} on m vertices.

The following claim will finish the proof of Lemma 2.5.

Claim 2.9. Algorithm E produces a graph J that is (ϱ, 3)-uniform in time ≤ Cm(log m)^{2}, where r = ϱm satisfies r_{0} ≤ r ≤ 2r_{0}, and C is a constant that depends only on r_{0}.

Proof. We start with the correctness of E. We already know that P produces suitable primes p and q. Hence, we only need to argue that the graph J obtained in Step 5 has the required properties.

By Theorem 2.6 and Corollary 2.7, the graph X^{p,q} constructed in Steps 2–4 has n = q(q^{2} − 1)/2 vertices, is (p + 1)-regular, and is (ϱ, 2)-uniform with ϱ = (p + 1)/n. Furthermore, note that (2.11) implies 1 ≤ n/m ≤ 1.05(1.1)^{3}. Lemma 2.1 implies J is a (ϱ, L)-uniform graph with ϱ = (p + 1)/n and L = 2\sqrt{n/m} ≤ 2.1\sqrt{231/200} = 2.256 ⋯ < 3. Thus J is indeed a (ϱ, 3)-uniform graph.

Since 1 ≤ n/m ≤ 1.05(1.1)^{3}, we deduce that r = ϱm = (p + 1)m/n is such that

r ≤ 2r_{0}

and

r ≥ 1.4r_{0} · \frac{20}{21} (\frac{10}{11})^{3} ≥ r_{0} .

Finally, we argue about the time complexity of each of the steps in Algorithm E. By Lemma 2.8, we already know that Step 1 takes time ≤ C_{1}(r_{0})m(log m)^{2}, where C_{1}(r_{0}) is a constant that depends only on r_{0}.

Recalling the form of the canonical representatives of the elements in PSL(2, ℤ/qℤ), we see that Step 2 may be performed in time O(m(log m)^{2}). The time complexity of Step 3 depends only on r_{0}.

In Step 4, we take one by one the vertices of X^{p,q}, i.e., the elements of PSL(2, ℤ/qℤ), and generate their adjacency lists. Since |T | = p + 1 ≤ 2r_{0}, to generate the adjacency list of a particular vertex takes only O((log q)^{2}) steps.

Finally, taking m vertices of X^{p,q} arbitrarily and adjusting their adjacency lists to create an adjacency list representation for the corresponding induced subgraph takes O(m log m) time. Therefore, the time complexity of Algorithm E is ≤ C_{0}(r_{0})m(log m)^{2}, as promised.

3. Algorithms. Before we describe the algorithm, let us introduce some notation. Let Γ = (V, E) be a graph and v ∈ V a vertex. We write Γ(v) for the neighborhood of v, i.e., for the set of all vertices adjacent to v in Γ, and d(v) for the degree of v, i.e. d(v) = |Γ(v)|. To shorten our notation we will use that same letter to denote a graph and the set of its edges. For example, Γ will also stand for E(Γ) and, hence, e(Γ) = |Γ|.

3.1. Regularity of bipartite graphs. In this section we describe algorithm A which takes as an input a bipartite graph G = (A, B; E), |A| = |B| = m, and 0 < ε < 1. The algorithm in time O(m^{2}) either confirms that G is ε-regular or finds sets A′ ⊆ A, B′ ⊆ B, |A′| ≥ ε′m, |B′| ≥ ε′m such that

|d(A′, B′) − d(A, B)| ≥ ε′ .

Our algorithm A consists of the preprocessing stage A_{P} and the main procedure A_{M}.

3.1.1. The preprocessing stage. In order to describe the preprocessing stage we need to define

ε′ = (\frac{ε}{10})^{20} \frac{1}{10^{4}} . (3.1)

To describe A_{P} we need the constants ε and ε′ only. Note that other constants are used for describing the other part A_{M}; these other constants will be defined later in §3.1.2 and will be related to ε and ε′ above.

Algorithm A_{P} is based on the following standard observation and Lemma 3.1. We observe that if the bipartite graph G on vertex set A ∪ B, |A| = |B| = m, is such that p(G) := d(A, B) = |G|/m^{2} ≤ ε^{3}, then G is ε-regular (we omit the proof of this standard observation).

Lemma 3.1 quantifies a further observation that we may remove some vertices of our graph G so that we either obtain a subgraph H ⊆ G that is essentially degreeregular (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 as follows.

Lemma 3.1. Suppose G is a bipartite graph with vertex set A∪B, |A| = |B| = m, and suppose that p(G) > ε^{3} holds. There is a procedure that runs in time O(m^{2}) that either (i) produces a witness to the ε′-irregularity of G or (ii) produces a bipartite subgraph H ⊆ G, say H = (U, V; F), such that

(a)

(1 − 2ε′)m < |U|, |V | ≤ m , (3.2)

(b)

|p(H) − p(G)| ≤ 5ε′, (3.3)

where p(H) = |H|/|U||V |, and

(c) for all u ∈ U and v ∈ V, we have

(3.4)  d(u) = (p(H) + O_{1}(10ε′)) · |V | ,
d(v) = (p(H) + O_{1}(10ε′)) · |U| .

Proof. We first omit the vertices v in V for which the condition

d(v) = (p(G) + O_{1}(ε′))m (3.5)

fails. If the number of such vertices is ≥ 2ε′m, we may easily produce a witness to the ε′-irregularity of G as in (i) in the statement of our lemma. Suppose therefore that the number of such vertices is < 2ε′m. Let V ⊆ B be the resulting subset of B. Hence |V | > (1 − 2ε′)m. We now omit the vertices u ∈ A for which the condition

d(u) = (p(G) + O_{1}(ε′)) · |V | (3.6)

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 (ii) in the statement of our lemma.

The time complexity assertion will be verified in the proof of Lemma 3.4 (cf. algorithm A_{P} below).

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

Now we are ready to describe algorithm A_{P}:

1. Given G and ε, decide if p(G) < ε^{3}.

2. If p(G) ≤ ε^{3}, then G is ε-regular and A_{P} halts.

3. If p(G) > ε^{3}, apply Lemma 3.1 to construct a subgraph H of G which satisfies (a)– (c). (Algorithm A_{M} will be applied to H. )

3.1.2. The main procedure. In view of step 3 in algorithm A_{P} (cf. Lemma 3.1) we will now assume that H ∈ Ψ(m, ε′).

(a) Definition of constants. Before describing algorithm A_{M} we will define constants needed for it. Recall that algorithm A, and so A_{M}, is given 0 < ε < 1. In §3.1.1 we already defined ε′ = (ε/10)^{20}/10^{4}.

We first let

δ = \frac{1}{4}(\frac{ε}{2})^{5}, L = 5, and r_{A} = \frac{10^{6}}{ε^{8}} . (3.7)

We now let

μ = (\frac{ε}{10})^{10} \frac{1}{100} (3.8)

and put

η = \frac{μ}{3} . (3.9)

We also let r_{B} = \overline{r}(η, L) be as given in Lemma 2.4 and let

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

Finally, we set

ε_{1} = \frac{1}{4} (\frac{ε}{2})^{16} . (3.11)

This will be used only later in a proof. However, it might be helpful to see the relation of ε_{1} to the other constants introduced here.

The reader may find it useful to keep in mind the following hierarchy of the constants for ε small:

ε′ < ε^{20} ≪ ε_{1} < ε^{16} ≪ η = \frac{μ}{3} < ε^{10} ≪ δ ≪ ε^{3} ≪ ε, p . (3.12)

(Here inequalities < are used to compare two quantities which differ by an absolute constant.) Note that for the description of A_{M} we only need to know r_{0} and δ defined above. The other constants are needed in the proofs below.

(b) Property P(J, δ). We introduce some notation. Let H be a bipartite graph with vertex set U ∪ V. Let J be a (ϱ, L)-uniform graph with vertex set U. We say that H has property P(J, δ) if

∑_{{u,u′}∈J} |d_{H}(u, u′) − p(H)^{2} · |V || ≤ δp(H)^{2}|V | · |J| (3.13)

holds. Recall that due to our notation {u, u′} ∈ J means that {u, u′} is an edge of J. Moreover, let us write J_{v} (v ∈ V) for the graph J[H(v)] induced by the neighbourhood H(v) of v in H. We define a 0–1 matrix M = (m(e, v))_{e,v} indexed by J × V as follows:

(3.14) m(e, v) = \begin{cases}1 & if e ∈ J_{v} \\ 0 & otherwise. \end{cases}

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

(c) Description of A_{M}. We assume A_{M} is given a bipartite graph H ∈ Ψ(m, ε′) having vertex set U ∪ V. Algorithm A_{M} now proceeds as follows:

1. Apply procedure E to construct a (ϱ, L)-uniform graph J with vertex set U and average degree r = ϱ · |U| satisfying

r_{0} = r_{0}(η) ≤ r ≤ 2r_{0} (3.15)

(cf. Lemma 2.5).

2. Verify whether H has P(J, δ). If it has, then then G is ε-regular (see Lemma 3.2 below) and A_{M} halts.

3. If P(J, δ) fails for H, construct matrix M = (m(e, v))_{e,v} defined above. Find and fix a vertex v_{0} ∈ V such that

∑_{v∈V} ∑_{e∈J_{v_{0}}} m(e, v) ≥ (1 + \frac{δ^{2}}{2} ) p(H)^{4}|V | · |J|. (3.16)

[The existence of such a vertex v_{0} is proved later, cf. Lemma 3.5.]

4. Set U′ = H(v_{0}) and

V′ = \{v′ ∈ V : ∑\{m(e, v′): e ∈ J_{v_{0}}\} ≥ (1 + \frac{δ^{2}}{4} ) p(H)^{4} · |J|\} . (3.17)

5. A_{M} outputs (U′, V′) and claims that this is a witness to the ε′-irregularity of G.

3.1.3. Correctness and analysis of Algorithm A. The correctness of A follows from Lemmas 3.2 and 3.3 below. The first lemma says that if Algorithm A_{M}, and hence A, claims that G is ε-regular in Step 2, then this is indeed the case.

Lemma 3.2. If H enjoys property P(J, δ), then G is ε-regular. Lemma 3.3. If property P(J, δ) fails for H, then G is not ε′-regular, and the

pair (U′, V′) produced by Algorithm A_{M} is indeed a witness for the ε′-irregularity of G.

We shall prove the two lemmas above in §4. The next two lemmas immediately imply that A has time complexity O(m^{2}).

Lemma 3.4. Algorithm A_{P} described in §3.1.1 has time complexity O(m^{2}). Proof. The steps of A_{P} have the following time complexity. The only computa-

tions are in steps 1 and 3: Step 1. Since p(G) = |G|/m^{2}, it takes at most O(m^{2}) steps to compute p(G) and

decide whether p(G) < ε^{3}. Step 3. Based on the proof of Lemma 3.1, a vertex of G is put into H iff it satis-

fies (3.4). Hence, we proceed through all 2m vertices of G each time checking (3.4) which takes O(m) steps. Thus, this step takes O(m^{2}) steps, too.

The overall time complexity of A_{P} is O(m^{2}).

Lemma 3.5. Algorithm A_{M} described in §3.1.2 runs in time O(m^{2}). Proof. The steps of A_{M} have the following time complexity:

Step 1. To perform procedure E we need O(m(log m)^{2}) steps, cf. Lemma 2.5. Step 2. To verify P(J, δ) we need to add |J| = O(m) summands. Computing each of

these summands takes O(m) steps. Consequently, one can decide P(J, δ) in O(m^{2}) time.

Step 3. Deciding if m(e, v) = 1 or 0 can be performed in constant time. Thus, constructing M takes O(|J||V |) = O(m^{2}) time. To check (3.16), we first write it in the equivalent form

∑_{e∈J_{v_{0}}} ∑_{v∈V} m(e, v) ≥ (1 + \frac{δ^{2}}{2} ) p(H)^{4}|V | · |J| . (3.18)

Using matrix M we compute the column sums ∑_{v∈V} m(e, v) for each e ∈ J. This takes O(m^{2}) steps. Now to check (3.18) for a fixed vertex v_{0} ∈ V, we first find J_{v_{0}}, which takes |J_{v_{0}}| = O(m) steps. Then we add together the column sums ∑_{v∈V} m(e, v) for all e ∈ J_{v_{0}} and decide about the truth of (3.18). This takes another O(m) steps. In the worst case we need to check all v_{0} ∈ V. Since |V | = m, to find v_{0} that satisfies (3.18) will take at most O(m^{2}) steps.

Step 4. Since for each v′ ∈ V the condition ∑_{e∈J_{v_{0}}} m(e, v′) ≥ (1 + δ^{2}/4)p(H)^{4}|J|

can be verified in O(m) time, the set V′ can be constructed in O(m^{2}) time. Step 5. This step takes a constant time. Therefore, the time complexity of A_{M} is O(m^{2}). Finally let us point out that the fact that J has O(m) edges was crucial.

3.2. The regularity lemma. For the sake of completeness, we include an algorithm necessary for proving Corollary 1.6. Given Theorem 1.5 we can derive the necessary algorithm in a standard way.

Let V_{0}, V_{1}, …, V_{k} be an equitable partition P of the set of vertices of a graph. We define the index of P, cf. [31], by

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

To present a proof of Corollary 1.6 we will use the following lemma, which was proved in [31]. Note that no comment is made in [31] on the running time. However, the proof of the lemma implies an algorithm of time complexity O(n).

Lemma 3.6. Fix k and γ and let G = (V, E) be a graph on 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γ^{−5}. 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 condition of γ-regularity of (V_{r}, V_{s})), then one can find in O(n) time an equitable partition P′ (which is a refinement of P) into 1 + k4^{k} classes, with the exceptional class of cardinality at most |V_{0}| + n/4^{k} and such that

ind(P′) ≥ ind(P) + \frac{γ^{5}}{20} .

Proof of Corollary 1.6. Theorem 1.5 and Lemma 3.6 already imply Corollary 1.6. Let ε > 0 and k_{0} be a positive integer. Let ε′ = ε^{20}/10^{24}. We set N = N(ε, k_{0}) and T = T (ε, k_{0}) as follows: Let a be the least positive integer such that

4^{a} > 600 (\frac{ε′}{4} )^{−5} , a ≥ k_{0} . (3.19)

Let k_{i} be a sequence of integers defined inductively as

k_{0} = a, k_{i+1} = k_{i}4^{k_{i}} .

Set T = k_{⌈10(ε′/4)^{−5}⌉} and N = max{T 4^{2T} , 2T/ε′^{2}}. Finally we set K′′_{0} = N ≥ T.

Let Γ = (V, E) be a graph on n vertices, n ≥ N. The following algorithm constructs an ε-regular partition of Γ into k + 1 classes with k_{0} ≤ k ≤ T ≤ K′′_{0}.

Algorithm A′_{0} proceeds as follows:

1. Arbitrarily divide the vertices of Γ into an equitable partition P_{1} with classes V_{0}, V_{1}, …, V_{a} where |V_{1}| = ⌊n/a⌋ and |V_{0}| < a. Set k_{1} = a.

2. For every pair (V_{r}, V_{s}) of P_{i}, verify if it is ε-regular or find V′_{r} ⊆ V_{r}, V′_{s} ⊆ V_{s}, |V′_{r}| ≥ (ε′/4)|V_{r}|, |V′_{s}| ≥ (ε′/4)|V_{s}|, such that |d(V′_{r}, V′_{s}) − d(V_{r}, V_{s})| ≥ ε′.

3. If there are at most ε\binom{k_{i}}{2} pairs that are not verified as ε-regular, then stop. The partition P_{i} is an ε-regular partition.

4. Apply Lemma 3.6 where P = P_{i}, k = k_{i}, γ = ε′/4 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.

Claim 3.7. Algorithm A′_{0} described is correct and runs in O(n^{2}) time.

Proof. To prove correctness of algorithm A′_{0} is quite standard. Since the index of partitions P_{i} constructed by A′_{0} strictly increases and at the same time is bounded by 1 from above, algorithm A′_{0} uses Lemma 3.6, and thus Theorem 1.5, only finitely many times. Each such use takes O(n^{2}) time.

4. Proofs of the main lemmas. We use the notation introduced in Section 3.1. Before the proofs let us point out a straightforward estimate on the size of neighborhoods used throughout the proofs.

Remark 4.1. Let H ∈ Ψ(m, ε′) be the graph in the statement of Lemma 3.1, and let and u ∈ U and v ∈ V be vertices of H. As an immediate consequence of (3.4) and the definition of ε′ and μ, we get

(4.1)  |H(u)| = (p(H) + O_{1}(10ε′))|V | = (1 + O_{1}(μ))p(H)|V | ,
|H(v)| = (p(H) + O_{1}(10ε′))|U| = (1 + O_{1}(μ))p(H)|U| .

4.1. Proof of Lemma 3.2. Let H ∈ Ψ(m, ε′) be the input graph of algorithm A_{M}. Let U ∪ V be the vertex set of H. Set m_{U} = |U|, m_{V} = |V |, and p := p(H) = |H|/m_{U}m_{V}.

We say that the graph H has property Q(J, δ) if the inequality

∑_{{u,u′}∈J} |d_{H}(u, u′) + p^{2}m_{V} − (d_{H}(u) + d_{H}(u′))p| ≤ δp^{2}m_{V} · |J| (4.2)

holds true.

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

Proof. Since H enjoys P(J, δ) and H ∈ Ψ(m, ε′), we have

∑_{{u,u′}∈J} |d_{H}(u, u′) + p^{2}m_{V} − (d_{H}(u) + d_{H}(u′))p|

≤ ∑_{{u,u′}∈J} |d_{H}(u, u′) − p^{2}m_{V} |

+2p ∑_{u∈U} |pm_{V} − d_{H}(u)|d_{J}(u)

≤ δp^{2}m_{V} |J| + 20pε′m_{V} ∑_{u∈U} d_{J}(u)

≤ 2δp^{2}m_{V} |J| ,

since ε′ ≤ δε^{3}/40 ≤ δp/40 (see (3.1, 3.7)).

In view of Claim 4.2, we are going to prove

Claim 4.3. Every H ∈ Ψ(m, ε′) that has property Q(J, 2δ) is (ε/2)-regular. The proof is presented below. First, let us observe that the ε/2-regularity of H

implies the ε-regularity of G. Indeed, let X ⊆ A, |X| ≥ ε|A|, and Y ⊆ B, |Y | ≥ ε|B|. Set X′ = X ∩ U and Y′ = Y ∩ V. By Lemma 3.1,

|X′| ≥ ε|A| − 2ε′|A| ≥ (ε − 2ε′)|U| ≥ \frac{ε}{2}|U|

and, similarly,

|Y′| ≥ \frac{ε}{2}|V | .

A standard argument based on the fact that X′ and Y′ are almost equal to X and Y (recall Lemma 3.1) shows that |d(X, Y) − d(X′, Y′)| ≤ ε/4. Thus, using the ε/2regularity of H and Lemma 3.1, we get

|d(X, Y) − d(A, B)| ≤ |d(X, Y) − d(X′, Y′)| + |d(X′, Y′) − d(U, V)|

+ |d(U, V) − d(A, B)| ≤ \frac{ε}{4} + \frac{ε}{2} + 5ε′ < ε .

Hence, G is ε-regular.

Proof of Claim 4.3. Let 𝔸 = (a_{u,v})_{u,v} be a matrix indexed by U ×V, with entries

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

Moreover, for u ∈ U, let ξ_{u} = (a_{u,1}, …, a_{u,m_{V}}) be the u-th row of 𝔸. The following claim follows easily from the definition of property Q (see (4.2)).

Claim 4.4. For every H ∈ Ψ(m, ε′) that has property Q(J, 2δ), the row-vectors of 𝔸 satisfy the following inequality

∑_{{u,u′}∈J} |⟨ξ_{u}, ξ_{u′}⟩| ≤ 2δp^{2}m_{V} |J| . (4.3)

Proof. Since

⟨ξ_{u}, ξ_{u′}⟩ = d_{H}(u, u′)(1 − p)^{2} − (d_{H}(u) + d_{H}(u′) − 2d_{H}(u, u′))p(1 − p)
+(m_{V} − (d_{H}(u) + d_{H}(u′) − d_{H}(u, u′))p^{2}
= d_{H}(u, u′)[(1 − p)^{2} + 2p(1 − p) + p^{2}] + m_{V} p^{2} − (d_{H}(u) + d_{H}(u′))p
= d_{H}(u, u′) + m_{V} p^{2} − (d_{H}(u) + d_{H}(u′))p

for any pair of vertices u, u′ ∈ U, we have that ∑_{{u,u′}∈J} |⟨ξ_{u}, ξ_{u′}⟩| equals the sum on the left hand side of (4.2). Thus the claim follows.

Let U′ ⊆ U and V′ ⊆ V. To shorten our notation ∑_{u,u′∈J}^{U′} will denote summation over {u, u′} ∈ J such that u, u′ ∈ U′. Furthermore, for u ∈ U′ let ψ_{u} be the restriction of the vector ξ_{u} to V′, i.e., ψ_{u} = (a_{u,v})_{v∈V′}. We clearly have ∑_{u,u′∈J}^{U′} |⟨ξ_{u}, ξ_{u′}⟩| ≤

∑_{{u,u′}∈J} |⟨ξ_{u}, ξ_{u′}⟩|. We now compare ∑_{u,u′∈J}^{U′}⟨ξ_{u}, ξ_{u′}⟩ with ∑_{u,u′∈J}^{U′}⟨ψ_{u}, ψ_{u′}⟩. We have

∑_{u,u′∈J}^{U′}⟨ξ_{u}, ξ_{u′}⟩ = ∑_{u,u′∈J}^{U′}⟨ψ_{u}, ψ_{u′}⟩ + ∑_{v∉V′} ∑_{u,u′∈J}^{U′} a_{u,v}a_{u′,v}. (4.4)

For v ∈ V we set S_{v}^{U′} = ∑_{u,u′∈J}^{U′} a_{u,v}a_{u′,v}, and proceed to estimate this quantity. Let S := H(v)∩U′ ⊆ U′ be the set of neighbours of the vertex v in U′ and T := (U′ \S) ⊆ U′ be the set of non-neighbours of the vertex v in U′.

Set α = |S|/|U′| and β = |T |/|U′|. Note α + β = 1. Thus we can write

S_{v}^{U′} = e_{J}(S)(1 − p)^{2} + e_{J}(T)p^{2} − e_{J}(S, T)p(1 − p). (4.5)

The (ϱ, L)-uniformity of J implies the following claim. Recall that for two numbers a, b we write a = O_{1}(b) if and only if |a| ≤ b.

Claim 4.5. For all v ∈ V′ and U′ ⊆ U, we have

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

Proof. Set m′ = |U′|. Since J is a (ϱ, L)-uniform graph, Lemma 2.3 implies

e_{J}(S) = \frac{ϱ}{2}|S|^{2} + O_{1}(2L\sqrt{r} · |S|)
= \frac{ϱ}{2}(αm′)^{2} + O_{1}(2L\sqrt{r} · αm′) ,
e_{J}(T) = \frac{ϱ}{2}|T |^{2} + O_{1}(2L\sqrt{r} · |T |)
= \frac{ϱ}{2}(βm′)^{2} + O_{1}(2L\sqrt{r} · βm′) ,
e_{J}(S, T) = ϱ|S| · |T | + O_{1}(L\sqrt{r|S| · |T |})
= ϱαβ(m′)^{2} + O_{1}(L\sqrt{rαβ} · m′) .

Using (4.5) we get

S_{v}^{U′} = [\frac{ϱ}{2}(αm′)^{2} + O_{1}(2L\sqrt{r} · αm′)](1 − p)^{2}

+[\frac{ϱ}{2}(βm′)^{2} + O_{1}(2L\sqrt{r} · βm′)]p^{2}

−[ϱαβ(m′)^{2} + O_{1}(L\sqrt{rαβ} · m′)]p(1 − p) (4.7)

= \frac{ϱ}{2}(m′)^{2}[α(1 − p) − βp]^{2} + Δ,

where

Δ = O_{1}(2L\sqrt{r} · αm′(1 − p)^{2} + 2L\sqrt{r} · βm′p^{2} + L\sqrt{rαβ} · m′p(1 − p)) . (4.8)

To bound Δ we are going to use the inequalities α(1 − p)^{2} + βp^{2} ≤ α + β and \sqrt{αβ} ≤ (α + β). Thus,

|Δ| ≤ 2L\sqrt{r} · αm′(1 − p)^{2} + 2L\sqrt{r} · βm′p^{2} + L\sqrt{rαβ} · m′p(1 − p)
≤ L\sqrt{r}m′(2α + 2β + \sqrt{αβ})
(4.9)  ≤ L\sqrt{r}m′ · 3(α + β)
= 3L\sqrt{r}m′ .

Expressions (4.7) and (4.9) already imply the claim. We only note that we got a bound on Δ linear in m′ = |U′| since L and r are constants.

Next we proceed with an upper and lower bounds on ∑_{u,u′∈J}^{U′}⟨ψ_{u}, ψ_{u′}⟩. To derive

an upper bound for this quantity we use (4.4) to relate ∑_{u,u′∈J}^{U′}⟨ψ_{u}, ψ_{u′}⟩ and S_{v}^{U′} as follows:

∑_{u,u′∈J}^{U′}⟨ψ_{u}, ψ_{u′}⟩ = ∑_{u,u′∈J}^{U′}⟨ξ_{u}, ξ_{u′}⟩ − ∑_{v∉V′} S_{v}^{U′}.

Note that (4.6) implies S_{v}^{U′} ≥ −3L\sqrt{r}|U′|. This lower bound and Claim 4.4 imply

∑_{u,u′∈J}^{U′}⟨ψ_{u}, ψ_{u′}⟩ ≤ 2δp^{2}m_{V} |J| + 3L\sqrt{r}|U′|(m_{V} − |V′|) . (4.10)

To estimate ∑_{u,u′∈J}^{U′}⟨ψ_{u}, ψ_{u′}⟩ from below, we first write

∑_{u,u′∈J}^{U′}⟨ψ_{u}, ψ_{u′}⟩ = ∑_{v∈V′} ∑_{u,u′∈J}^{U′} a_{u,v}a_{u′,v} = ∑_{v∈V′} S_{v}^{U′} . (4.11)

Using (4.6) we get a lower bound on the expression in our last equation

∑_{u,u′∈J}^{U′}⟨ψ_{u}, ψ_{u′}⟩ = ∑_{v∈V′} S_{v}^{U′}
(4.12)  ≥ ∑_{v∈V′}(\frac{ϱ}{2}|U′|^{2}[α(1 − p) − βp]^{2} − 3L\sqrt{r} · |U′|)

≥ \frac{ϱ}{2} · \frac{|U′|^{2}}{|V′|} [ ∑_{v∈V′}(α(1 − p) − βp)]^{2} − 3L\sqrt{r}|U′| · |V′| .

We used the Cauchy–Schwarz inequality to get the last line of our bound. Comparing the lower and upper bounds on ∑_{u,u′∈J}^{U′}⟨ψ_{u}, ψ_{u′}⟩, cf. (4.12) and (4.10), we infer

[ ∑_{v∈V′}(α(1 − p) − βp)]^{2} ≤ \frac{2|V′|}{ϱ|U′|^{2}} · (2δp^{2}m_{V} |J| + 3L\sqrt{r}|U′|m_{V} ) . (4.13)

Now we are ready to show that H is \frac{ε}{2}-regular. Fix U′ ⊆ U, |U′| ≥ \frac{ε}{2}|U| = \frac{ε}{2}m_{U}, and V′ ⊆ V, |V′| ≥ \frac{ε}{2}|V | = \frac{ε}{2}m_{V}. Recall that d(U, V) = p = p(H) in our notation. First we relate the difference of densities to the left-hand side of (4.13) as follows:

|d(U′, V′) − d(U, V)|^{2} = |\frac{e(U′, V′)}{|U′||V′|} − p|^{2}
= \frac{1}{|U′|^{2}|V′|^{2}} [e(U′, V′) − p|U′| · |V′|]^{2}
= \frac{1}{|U′|^{2}|V′|^{2}} [ ∑_{v∈V′}(|H(v) ∩ U′| − p|U′|)]^{2}

= \frac{1}{|U′|^{2}|V′|^{2}} [ ∑_{v∈V′} α|U′| − p|U′|]^{2}

(4.14)  = \frac{1}{|V′|^{2}} [ ∑_{v∈V′}(α(1 − p) − βp)]^{2} .

Finally, we bound the expression for the difference of densities in (4.14) using (4.13). We get

|d(U′, V′) − d(U, V)|^{2} ≤ \frac{2}{ϱ|U′|^{2}|V′|} (2δp^{2}m_{V} |J| + 3L\sqrt{r} · |U′|m_{V} )
≤ \frac{2}{ϱ|U′|^{2}|V′|} × 2δp^{2}m_{V} × \frac{rm_{U}}{2} + \frac{6L\sqrt{r} · |U′|m_{V}}{ϱ|U′|^{2}|V′|}
≤ \frac{2δp^{2}m_{U}^{2}m_{V}}{|U′|^{2}|V′|} + \frac{6Lm_{V} m_{U} \sqrt{r}}{r|U′| · |V′|}
≤ \frac{16δ}{ε^{3}} + \frac{24L}{\sqrt{r} · ε^{2}}
≤ \frac{1}{2} · (\frac{ε}{2})^{2} + \frac{1}{2} · (\frac{ε}{2})^{2}
= (\frac{ε}{2})^{2} .

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

4.2. Proof of Lemma 3.3. For this proof, the reader may find it convenient to recall the hierarchy of the constants given in (3.12). Recall we have

p = p(H) = p(G) + O_{1}(5ε′) ≥ \frac{1}{2}ε^{3}. (4.15)

Note that (4.15) is guaranteed to hold for the graph H that we obtain after preprocessing H as described in §3.1.1 since p(G) ≥ ε^{3} in this case. As in §3.1.2 we assume U ∪ V is the vertex set of H and set m_{U} = |U| and m_{V} = |V |.

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

∑_{{u,u′}∈J} |d_{H}(u, u′) − p^{2}m_{V} | > δp^{2}m_{V} |J| . (4.16)

Let us first observe that

∑_{{u,u′}∈J} (d_{H}(u, u′) − p^{2}m_{V} )^{2}

= ∑_{{u,u′}∈J} (d_{H}(u, u′)^{2} − 2d_{H}(u, u′)p^{2}m_{V} + p^{4}m_{V} ^{2}) (4.17)

= ∑_{{u,u′}∈J} d_{H}(u, u′)^{2} − 2p^{2}m_{V} ∑_{{u,u′}∈J} d_{H}(u, u′) + p^{4}m_{V} ^{2}|J| .

However,

∑_{{u,u′}∈J} d_{H}(u, u′) = ∑_{{u,u′}∈J} |H(u) ∩ H(u′)|
= ∑_{v∈V} |J_{v}| = ∑_{v∈V}(1 + O_{1}(η))(1 + O_{1}(μ))^{2}p^{2}|J| .

In the last inequality we used that due to preprocessing, cf. (4.1), |H(v)| = (1 + O_{1}(μ))pm_{U} and, hence (a) in Lemma 2.4 gives (note that (1 + O_{1}(μ))p ≥ η)

|J_{v}| = (1 + O_{1}(η))(1 + O_{1}(μ))^{2}p^{2}|J| = (1 + O_{1}(3μ))p^{2}|J| .

22 Y. KOHAYAKAWA, V. RÖDL, L. THOMA

Therefore

∑_{{u,u′}∈J} d_{H}(u, u′) = (1 + O_{1}(3μ))p^{2}m_{V} |J| . (4.18)

From (4.17) and (4.18) we obtain that

∑_{{u,u′}∈J} (d_{H}(u, u′) − p^{2}m_{V} )^{2}

= ∑_{{u,u′}∈J} d_{H}(u, u′)^{2} − (1 + O_{1}(6μ))p^{4}m_{V} ^{2}|J| (4.19)

≤ ∑_{\{u,u′\}∈J} d_{H}(u, u′)^{2} − (1 − \frac{δ^{2}}{2} ) p^{4}m_{V} ^{2}|J| .

The last inequality holds true due to our choices of δ and μ, cf. (3.7, 3.8). On the other hand, in view of (4.16), we have by the Cauchy–Schwarz inequality that

∑_{\{u,u′\}∈J} (d_{H}(u, u′) − p^{2}m_{V} )^{2} ≥ \frac{1}{|J|}( ∑_{\{u,u′\}∈J} |d_{H}(u, u′) − p^{2}m_{V} |)^{2}
(4.20)  > \frac{1}{|J|} (δ|J|p^{2}m_{V} )^{2} = δ^{2}p^{4}m_{V} ^{2}|J| .

Comparing (4.19) and (4.20), we deduce that

∑_{\{u,u′\}∈J} d_{H}(u, u′)^{2} ≥ (1 + \frac{δ^{2}}{2} ) p^{4}m_{V} ^{2}|J| . (4.21)

We shall now evaluate the sum on the left-hand side of (4.21) in terms of the matrix M = (m(e, v))_{e,v} defined in §3.1.

Clearly, if e = {u, u′} ∈ J, then

d_{H}(u, u′) = |H(u) ∩ H(u′)| = ∑_{v∈V} m(e, v),

and hence

d_{H}(u, u′)^{2} = ∑_{v∈V} ∑_{v′∈V} m(e, v)m(e, v′) .

Therefore

(4.22) ∑_{{u,u′}∈J} d_{H}(u, u′)^{2} = ∑_{v∈V} ∑_{e∈J} m(e, v) ∑_{v′∈V} m(e, v′)
= ∑_{v∈V} ∑_{e∈J_{v}} ∑_{v′∈V} m(e, v′) = ∑_{v∈V} ∑_{v′∈V} ∑_{e∈J_{v}} m(e, v′) .

Comparing (4.21) and (4.22) we infer that

∑_{v∈V} ∑_{v′∈V} ∑_{e∈J_{v}} m(e, v′) ≥ (1 + \frac{δ^{2}}{2} ) p^{4}m_{V} ^{2}|J|

and, hence, there is a vertex v_{0} ∈ V for which we have

∑_{v′∈V} ∑_{e∈J_{v_{0}}} m(e, v′) ≥ (1 + \frac{δ^{2}}{2} ) p^{4}m_{V} |J| . (4.23)

Following the algorithm, we fix such a vertex v_{0}. We now set

V′ := \{ v′ ∈ V : ∑_{e∈J_{v_{0}}} m(e, v′) ≥ (1 + \frac{δ^{2}}{4} ) p^{4}|J| \} . (4.24)

As in the algorithm, we put U′ = H(v_{0}). One may prove that both U′ and V′ are large sets. The proof is postponed for the next section.

Claim 4.6. |U′| ≥ ε_{1}m_{U} and |V′| ≥ ε_{1}m_{V}.

Recall that we defined ε_{1} = \frac{1}{4}(\frac{ε}{2})^{16} in (3.11) to satisfy ε′ ≪ ε_{1} ≪ δ^{2}. Before we proceed, using the definition of matrix M we observe that for all v′ ∈ V we have

∑_{e∈J_{v_{0}}} m(e, v′) = e(J[H(v_{0}) ∩ H(v′)]) . (4.25)

Combining (4.25) and the fact that the edges of J are extremely well distributed we shall now provide a lower bound on d_{H}(v_{0}, v′) where v_{0} is the vertex fixed above and v′ is an arbitrary vertex of V′.

Claim 4.7. For all v′ ∈ V′, we have

d_{H}(v_{0}, v′) ≥ (1 + \frac{δ^{2}}{12}) p^{2}m_{U} . (4.26)

The proof of Claim 4.7 is given in next section. Since U′ = H(v_{0}), it follows immediately from Claim 4.7 that

e_{H}(U′, V′) ≥ (1 + \frac{δ^{2}}{12}) p^{2}m_{U}|V′| (4.27)

which implies that

d_{H}(U′, V′) = \frac{e_{H}(U′, V′)}{|U′||V′|} ≥ \frac{(1 + δ^{2}/12)p^{2}m_{U}|V′|}{(1 + μ)pm_{U}|V′|}
(4.28)  ≥ (1 + \frac{δ^{2}}{14}) p > p + ε_{1} .

Since we have already proved that |U′| ≥ ε_{1}m_{U} and |V′| ≥ ε_{1}m_{V} (see Claim 4.6), inequality (4.28) tells us that (U′, V′) is a witness to the ε_{1}-irregularity of H.

We shall now prove that (U′, V′) is in fact a witness to the ε′-irregularity of G. We have

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

and, similarly,

|V′| ≥ ε_{1}m_{V} ≥ ε_{1}(1 − 2ε′)m ≥ ε′m . (4.30)

Because of (3.3) and (4.28), we have

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

In view of (4.29,4.30) inequality (4.31) implies that (U′, V′) is indeed a witness to the ε′-irregularity of G, as required.

4.2.1. Proofs of Claims 4.6 and 4.7. Here we give proofs of Claims 4.6 and 4.7.

Proof of Claim 4.6. Since U′ = H(v_{0}), estimates (4.1) and our definition of ε_{1} imply |U′| = (1 + O_{1}(μ))pm_{U} ≥ ε_{1}m_{U}.

Now we will give a lower bound on |V′|. By the definition of V′, we have

∑_{v′∈V} ∑_{e∈J_{v_{0}}} m(e, v′) = ∑_{v′∉V′} ∑_{e∈J_{v_{0}}} m(e, v′) + ∑_{v′∈V′} ∑_{e∈J_{v_{0}}} m(e, v′)

(4.32)  < (1 + \frac{δ^{2}}{4} ) p^{4}|J|(m_{V} − |V′|) + |V′|e(J_{v′}) .

Since |H(v′)| = (1 + O_{1}(μ))pm_{V}, cf. (4.1), (a) in Lemma 2.4 implies (note (1 + O_{1}(μ))p ≥ η)

e(J_{v′}) = e(J[H(v′)]) = (1 + O_{1}(η))(1 + O_{1}(μ))^{2}p^{2}|J| = (1 + O_{1}(3μ))p^{2}|J| .

Thus continuing with (4.32) we can write

∑_{v′∈V} ∑_{e∈J_{v_{0}}} m(e, v′) < (1 + \frac{δ^{2}}{4} ) p^{4}|J|m_{V} + (1 + O_{1}(3μ))|V′|p^{2}|J| . (4.33)

Comparing (4.23) and (4.33), we obtain

2|V′| ≥ (1 + O_{1}(3μ))|V′| ≥ \frac{1}{4}δ^{2}p^{2}m_{V}

and this, using definition of δ and ε_{1}, gives

|V′| ≥ \frac{1}{8}δ^{2}p^{2}m_{V} ≥ \frac{1}{128} (\frac{ε}{2})^{10} ε^{6}m_{V} ≥ ε_{1}m_{V} ,

as required.

Proof of Claim 4.7. Suppose to the contrary that (4.26) fails, i.e., d_{H}(v_{0}, v′) < (1 + δ^{2}/12)p^{2}m_{U}. We distinguish two cases: If d_{H}(v_{0}, v′) ≥ ηm_{U}, then using (a) in Lemma 2.4 for H(v_{0}) ∩ H(v′) implies

e(J[H(v_{0}) ∩ H(v′)]) < (1 + O_{1}(η)) (1 + \frac{δ^{2}}{12})^{2} p^{4}|J| .

If, on the other hand, d(v_{0}, v′) < ηm_{U} we have (cf. (b) in Lemma 2.4)

e(J[H(v_{0}) ∩ H(v′)]) < 2η^{2}|J| .

In either case, we have

e(J[H(v_{0}) ∩ H(v′)]) < (1 + \frac{δ^{2}}{4} ) p^{4}|J| . (4.34)

However, in view of the definition of V′ (see (4.24, 4.25)), inequality (4.34) cannot hold. This contradiction shows that (4.26) must indeed hold.

Acknowledgements. The authors are grateful to the referee for his or her detailed comments.

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(1) (1994), 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] , Efficient testing of large graphs, Combinatorica, 20(1) (2000), pp. 451–476.

[5] N. Alon and J. Spencer, The probabilistic method, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, New York, 1992.

[6] F. R. K. Chung and R. L. Graham, Quasi-random set systems, J. Amer. Math. Soc., 4(1) (1991), pp. 151–196.

[7] , Quasi-random tournaments, J. Graph Theory, 15(2) (1991), pp. 173–198.

[8] , Quasi-random subsets of Z_{n}, J. Combin. Theory Ser. A, 61(1) (1992), pp. 64–86.

[9] , Sparse quasi-random graphs, Combinatorica, 22(2) (2002), pp. 217–244.

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

[11] Don Coppersmith and Shmuel Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput., 9(3) (1990), pp. 251–280.

[12] A. Czumaj and C. Sohler, Testing hypergraph coloring, Proc. of ICALP, 2001, pp. 493–505.

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

[14] W. Fernandez de la Vega, MAX-CUT has a randomized approximation scheme in dense graphs, Random Structures Algorithms, 8(3) (1996), pp. 187–198.

[15] 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(3) (1995), pp. 598–620.

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

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

[18] Alan Frieze and Ravi 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.

[19] , Quick approximation to matrices and applications, Combinatorica, 19(2) (1999), pp. 175–220.

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

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

[22] Oded Goldreich, Shafi Goldwasser, and Dana 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.

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

[24] Y. Kohayakawa and V. Rödl, Szemerédi’s regularity lemma and quasi-randomness, Recent advances in algorithms and combinatorics, CMS Books Math./Ouvrages Math. SMC, vol. 11, Springer, New York, 2003, pp. 289–351.

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

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

[27] , Ramanujan graphs, Combinatorica, 8(3) (1988), pp. 261–277.

[28] M. Luby and A. Wigderson, Pairwise independence and derandomization, Tech. Report 95-035, International Computer Science Institute, July 1995.

[29] J. Spencer, Optimal ranking of tournaments, Networks, 1 (1971), pp. 135–138.

[30] , Nonconstructive methods in discrete mathematics, Studies in Combinatorics (G.C. Rota, ed.), Mathematical Association of America, Washington, D.C., 1978, pp. 142–178.

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

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