SZEMERÉDI’S REGULARITY LEMMA AND QUASI-RANDOMNESS

Y. KOHAYAKAWA AND V. RÖDL

Abstract. The first half of this paper is mainly expository, and aims at introducing the regularity lemma of Szemerédi. Among others, we discuss an early application of the regularity lemma that relates the notions of universality and uniform distribution of edges, a form of ‘pseudorandomness’ or ‘quasi-randomness’. We then state two closely related variants of the regularity lemma for sparse graphs and present a proof for one of them.

In the second half of the paper, we discuss a basic idea underlying the algorithmic version of the original regularity lemma: we discuss a ‘local’ condition on graphs that turns out to be, roughly speaking, equivalent to the regularity condition of Szemerédi. Finally, we show how the sparse version of the regularity lemma may be used to prove the equivalence of a related, local condition for regularity. This new condition turns out to give a O(n^{2}) time algorithm for testing the quasi-randomness of an n-vertex graph.

Contents

1. Introduction 2 1.1. Remarks on notation and terminology 4 Acknowledgement 4 2. The regularity lemma 4 2.1. Preliminary definitions and the regularity lemma 4 2.1.1. Some remarks on Theorem 4 5 2.1.2. Irregular pairs and the number of blocks in regular partitions 7 2.2. A regularity lemma for sparse graphs 8 2.3. A second regularity lemma for sparse graphs 9 3. An application of the regularity lemma 9 3.1. A simple fact about almost all graphs 9 3.2. The statement of the results 10 3.2.1. Proof of Theorem 20 11 3.2.2. An application in Ramsey theory 14 3.2.3. Uniform edge distribution and subgraph frequency 15 3.3. The proof of Theorem 18 15 3.3.1. The embedding lemma 15 3.3.2. Proof of Theorem 18 18 4. Further applications 19 4.1. Embedding large bounded degree graphs 19 4.2. Property testing 20 4.2.1. Definitions and the testability result 21 4.2.2. A variant of the regularity lemma 22 5. Proof of the regularity lemma 23 5.1. The refining procedure 23 5.2. Defect form of the Cauchy–Schwarz inequality 25 5.3. The index of a partition 26

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 collaboration between the authors is supported by a CNPq/NSF cooperative grant.

5.4. The index of subpartitions 26 5.4.1. The draw case 26 5.4.2. The winning case 27 5.5. Proof of Theorem 13 28 6. Local conditions for regularity 29 6.1. The basic argument 29 6.2. The converse 31 6.3. The general results 32 6.3.1. The sufficiency of the condition 32 6.3.2. The necessity of the condition 33 6.4. Algorithmic versions 33 6.4.1. A coNP-completeness result 34 6.5. The sparse case 35 7. A new quasi-random property 35 7.1. Basic definitions 35 7.2. The equivalence result 36 7.3. The existence of (ϱ, A)-uniform graphs 37 7.4. Proof of Theorem 56 38 7.5. Proof of Theorem 57 41 References 48

1. Introduction

A beautiful result of Szemerédi on the asymptotic structure of graphs is his regularity lemma. Roughly speaking, this result tells us that any large graph may be written as a union of induced, random looking bipartite graphs. There are many applications of this result—the reader is urged to consult the excellent survey of Komlós and Simonovits [42] for a thorough discussion on this fundamental result.

The original regularity lemma is best suited for attacking problems involving ‘dense’ graphs, that is, n-vertex graphs with ≥ cn^{2} edges for some constant c > 0. In the case of ‘sparse graphs’, that is, n-vertex graphs with o(n^{2}) edges, one has to adapt the definitions to take into account the vanishing density of the graphs in question. It turns out that regularity lemmas for certain classes of such sparse graphs may be proved easily. More importantly, such results turned out to be quite important in dealing with certain extremal and Ramsey type problems involving subgraphs of random graphs. The interested reader is referred to [36].

One of our aims in this paper is to focus on a circle of ideas that concern ‘local’ characterizations of regularity, which we believe should be better known. One tool that will be required is the regularity lemma for sparse graphs. Since we would also like this paper to be useful as an introduction to the regularity lemma, we include some expository sections.

The contents of this paper fall naturally into four parts. We start by presenting the basic concepts and the statement of the regularity lemma in Section 2.1. In Sections 2.2 and 2.3, we state two variants of the regularity lemma for sparse graphs.

If the reader is not too familiar with the regularity lemma, we suggest skipping Sections 2.2 and 2.3 at first, and advancing directly to the second part of this paper, Section 3, where we discuss in detail an application of the regularity lemma in its original form. The result we prove in Section 3, which closely follows parts of [55], shows that if the edges of a graph are ‘uniformly distributed’, then the graph must have a rich subgraph structure. This result, Theorem 18, will be used to confirm a conjecture of Erdős and we shall also mention a classical result in Ramsey theory that may be deduced easily from this result. We believe that Theorem 18 also illustrates the importance of the notion of ‘quasi-randomness’, addressed later in Section 7. The proof of Theorem 18 also illustrates a typical application of the regularity lemma. We hope that the uninitiated readers who are interested in regularity will study this proof in detail.

In Section 4 we mention some other applications of the regularity lemma that have emerged more recently. Our choice of topics for Section 4 has to do in part with the ideas and techniques that appear in Section 3 and some natural questions that they suggest. One application we discuss has an algorithmic flavour (see Section 4.2). In the following section, Section 5, we prove the version of the regularity lemma for sparse graphs given in Section 2.2.

In the third part of this paper, Section 6, we discuss a key fact that states that a certain local property of bipartite graphs is, roughly speaking, equivalent to the property of being regular in the sense of Szemerédi. This fact was the key tool for the development of the algorithmic version of the regularity lemma.

In the final part of this paper, Section 7, we discuss a new quasi-random graph property, by which we mean, following Chung, Graham, and Wilson [15], a property that belongs to a certain rather large and disparate collection of equivalent graph properties, shared by almost all graphs. To prove that our property is a quasirandom property in the sense of [15], we shall make use of the sparse regularity lemma.

A few remarks are in order. To focus on the main point in Section 6, we carry out our discussion on the local condition for regularity restricting ourselves to the very basic case, namely, the case of n by n bipartite graphs with edge density 1/2. In fact, for the sake of convenience, instead of talking about bipartite graphs, we shall consider n by n matrices whose entries are are +1s and −1s (and whose density of +1s will turn out to be ∼ 1/2). We shall see that if the rows of a {±1}-matrix are pairwise orthogonal, then the matrix has small discrepancy, which may be thought of as an indication that our matrix is ‘random looking’. The reader may find a fuller discussion of this in Frankl, Rödl, and Wilson [26].

The relevance of the ideas in Section 6 may be illustrated by the fact that several authors have made use of them, in some form, in different contexts; see [1, 2, 4, 5, 10, 15, 19, 62, 63] and the proof of the upper bound in Theorem 15.2 in [22], due to J. H. Lindsey. We believe that these ideas should be carried over to the sparse case in some way as well, since this may prove to be quite fruitful; the interested reader is referred to [38, 39] and to Alon, Capalbo, Kohayakawa, Rödl, Ruciński, and Szemerédi [3].

We hope that our discussion in Section 6 will naturally lead the reader to the results in the final part of the paper, namely, the results concerning our quasirandom graph property. Indeed, Sections 6.1 and 6.2, which capture the essence of our discussion in Section 6, are quite gentle and we hope that the reader will find them useful as a preparation for the technically more involved Section 7. Before we close the introduction, we mention that our quasi-random property allows one to check whether an n-vertex graph is quasi-random in time O(n^{2}). The fastest algorithms so far had time complexity O(M(n)) = O(n^{2.376}), where M(n) denotes the time needed to square a {0, 1}-matrix over the integers [17]. Furthermore, in a forthcoming paper with Thoma [41], we shall present how this quasi-random property may be used to develop a deterministic O(n^{2}) time algorithm for the regularity lemma, improving on the result of Alon, Duke, Lefmann, Rödl, and Yuster [4, 5]. The reader is referred to [37] for a discussion on the algorithmic aspects of regularity.

1.1. Remarks on notation and terminology. If δ > 0, we write A ∼_{δ} B to mean that

\frac{1}{1 + δ} B ≤ A ≤ (1 + δ)B.  (1)

We shall use the following non-standard notation: we shall write O_{1}(x) for any term y that satisfies |y| ≤ x. Clearly, if A ∼_{δ} B, then A = (1 + O_{1}(δ))B.

Given an integer n, we write [n] for the set {1, …, n}. If X is a set and k is an integer, we write \binom{X}{k} for the set of all k-element subset of X. We write X △ Y for the symmetric difference (X \ Y) ∪ (Y \ X) of the sets X and Y.

We usually write G^{n} for a graph on n vertices. We denote the complete graph on k vertices by K^{k}. We usually write e(G) for the number of edges in the graph G. We denote the set of neighbours of a vertex x in a graph G by Γ(x) = Γ_{G}(x). If G is a graph and \{u, w\} ∈ E(G) ⊂ \binom{V (G)}{2} is an edge of G, we often write uw and wu for this edge {u, w}. Sometimes we write B = (U, W; E) for a bipartite graph B with a fixed bipartition V (B) = U ∪ W, where E = E(B).

As customary, if G = (V, E) and H = (U, F) are graphs with U ⊂ V and F ⊂ E, then we say that H is a subgraph of G, and we write H ⊂ G. Moreover, if U = V, then we say that H is a spanning subgraph of G. If W ⊂ V, then the subgraph of G induced by W in G is the subgraph

(W, E ∩ \binom{W}{2}) ,  (2)

usually denoted by G[W]. A subgraph H of G is an induced subgraph if H = G[V (H)], that is, every edge of G that has both its endpoints in the vertex set V (H) of H is necessarily an edge of H as well.

Acknowledgement. The authors are very grateful to the editors of this volume for their extreme patience.

2. The regularity lemma

Our aim in this section is to present the original regularity lemma of Szemerédi and two closely related versions of the regularity lemma for sparse graphs.

2.1. Preliminary definitions and the regularity lemma. Let a graph G = G^{n} of order |V (G)| = n be fixed. For U, W ⊂ V = V (G), we write E(U, W) = E_{G}(U, W) for the set of edges of G that have one endvertex in U and the other in W. We set e(U, W) = e_{G}(U, W) = |E(U, W)|. The rather natural concept of density d(U, W) = d_{G}(U, W) of a pair (U, W) in G is defined as follows: for any two disjoint non-empty sets U, W ⊂ V, we let

d_{G}(U, W) = \frac{e_{G}(U, W)}{|U||W |}.  (3)

Szemerédi’s regularity lemma asserts the existence of partitions of graphs into a bounded number of remarkably ‘uniform’ pieces, known as ε-regular pairs.

Definition 1 (ε-regular pair). Let 0 < ε ≤ 1 be a real number. Suppose G is a graph and U and W ⊂ V = V (G) are two disjoint, non-empty sets of vertices of G. We say that the pair (U, W) is (ε, G)-regular, or simply ε-regular, if we have

|d_{G}(U′, W′) − d_{G}(U, W)| ≤ ε  (4)

for all U′ ⊂ U and W′ ⊂ W with

|U′| ≥ ε|U| and |W′| ≥ ε|W |.  (5)

If a pair (U, W) fails to be ε-regular, then a pair (U′, W′) that certifies this fact is called a witness for the ε-irregularity of (U, W). Thus, if (U′, W′) is such a witness, then (5) holds but (4) fails.

In the regularity lemma, the vertex set of the graphs will be partitioned into a bounded number of blocks, basically all of the same size.

Definition 2 ((ε, k)-equitable partition). Given a graph G, a real number 0 < ε ≤ 1, and an integer k ≥ 1, we say that a partition Q = (C_{i})_{0}^{k} of V = V (G) is (ε, k)- equitable if we have

(i) |C_{0}| ≤ εn, (ii) |C_{1}| = … = |C_{k}|.

The class C_{0} is referred to as the exceptional class of Q.

When the value of ε is not relevant, we refer to an (ε, k)-equitable partition as a k-equitable partition. Similarly, Q is an equitable partition of V if it is a k-equitable partition for some k. We may now introduce the key notion of ε-regular partitions for the graph G.

Definition 3 (ε-regular partition). Given a graph G, we say that an (ε, k)-equitable partition Q = (C_{i})_{0}^{k} of V = V (G) is (ε, G)-regular, or simply ε-regular, if at most ε\binom{k}{2} pairs (C_{i}, C_{j}) with 1 ≤ i < j ≤ k are not ε-regular.

We may now state the celebrated lemma of Szemerédi [60].

Theorem 4 (The regularity lemma). For any given ε > 0 and k_{0} ≥ 1, there are constants K_{0} = K_{0}(ε, k_{0}) ≥ k_{0} and N_{0} = N_{0}(ε, k_{0}) such that any graph G = G^{n} with n ≥ N_{0} vertices admits an (ε, G)-regular, (ε, k)-equitable partition of its vertex set with k_{0} ≤ k ≤ K_{0}.

We shall not prove Theorem 4 here. However, a proof of a generalization of this result will be presented in detail later (see Section 5).

2.1.1. Some remarks on Theorem 4. Before we proceed, we make a few quite simple remarks on the concept of regularity and on the formulation of Theorem 4. The remarks below are primarily intended for the readers with little familiarity with the regularity lemma.

Remark 5. Let B = (U, W; E) be a bipartite graph with vertex classes U and W and edge set E. Suppose |U| = |W | = m and, say, |E| = ⌊m^{2}/2⌋. Is such a graph typically ε-regular? I.e., is the pair (U, W) typically ε-regular? It turns out that this is indeed the case.

Fact 6. Let B(U, W; m, M) be the collection of all bipartite graphs B = (U, W; E) on a fixed pair of sets U and W with |U| = |W | = m and |E| = M. For 0 < ε ≤ 1, let R(U, W; m, M; ε) ⊂ B(U, W; m, M) be the set of all ε-regular bipartite graphs in B(U, W; m, M). If 0 < ε ≤ 1 is a fixed constant and M(m) is such that, say,

lim_{m→∞} M(m)/m^{2} = p,  (6)

where 0 < p < 1, then

lim_{m→∞} \frac{|R(U, W; m, M(m); ε)|}{|B(U, W; m, M(m))|} = 1.  (7)

The result above tells us that ‘almost all’ (dense) bipartite graphs are ε-regular. Fact 6 follows easily from standard large deviation inequalities. The reader is referred to, say, Chapter 7 of [12, 14] (the well-known monographs [13, 35] will also certainly do).

Remark 7. Bipartite graphs that are very sparse are necessarily ε-regular. We may make this observation precise as follows. Suppose B = (U, W; E) ∈ B(U, W; m, M), where d(U, W) = M/m^{2} ≤ ε^{3}. Then B is automatically ε-regular. Indeed, a witness (U′, W′) to the ε-irregularity of (U, W) must be such that

d(U′, W′) > d(U, W) + ε ≥ ε.  (8)

Therefore e(U, W) ≥ e(U′, W′) ≥ d(U′, W′)|U′||W′| > ε|U′||W′| ≥ ε^{3}m^{2}. However, by assumption, e(U, W) = M ≤ ε^{3}m^{2}. This contradiction shows that such a witness cannot exist. Therefore B is indeed ε-regular.

It should be also clear that bipartite graphs that are very dense are also automatically ε-regular. The reader is invited to work out the details.

Remark 8. Suppose we have a graph G = G^{n}. Trivially, any k-equitable partition of V (G) with k = 1 is ε-regular. However, in an ε-regular partition (C_{i})_{0}^{k} for G, we do not have any information about the edges incident to the exceptional class C_{0}, nor do we have any information about the edges contained within the C_{i} (1 ≤ i ≤ k). Therefore the 1-equitable partitions of G are of no interest. The lower bound k_{0} in the statement of Theorem 4 may be used to rule out partitions into a small number of blocks.

In fact, the number of edges within the C_{i} (1 ≤ i ≤ k) in an (ε, k)-equitable partition is at most k^{−1}\binom{n}{2} ≤ k_{0}^{−1}\binom{n}{2}, and the number of edges incident to C_{0} is at most εn^{2}, since |C_{0}| ≤ εn. Therefore, one usually chooses k_{0} and ε so that

\frac{1}{k_{0}} \binom{n}{2} + εn^{2}  (9)

is a negligible number of edges for the particular application in question.

Remark 9. Let G = G^{n} be a given graph. Sometimes it is a little more convenient to consider regular partitions for G in which no exceptional class is allowed. One may instead require that the partition (C_{i})_{1}^{k} of V = V (G) should be such that

⌊\frac{n}{k}⌋ ≤ |C_{1}| ≤ ⋯ ≤ |C_{k}| ≤ ⌈\frac{n}{k}⌉ ,  (10)

and such that ≥ (1 − ε)\binom{k}{2} of the pairs (C_{i}, C_{j}) with 1 ≤ i < j ≤ k are ε-regular. We leave it as an exercise to deduce this version of the regularity lemma from Theorem 4.

Remark 10. Suppose we allow regular partitions as in Remark 9 above. Then, as a side effect, we may omit the condition that the graph G = G^{n} should satisfy n ≥ N_{0}(ε, k_{0}). Indeed, it suffices to use the fact that the partition of the vertex set of a graph into singletons is ε-regular. Indeed, let K_{0} = K_{0}(ε, k_{0}) be the upper bound for the number of classes in the ε-regular partitions with at least k_{0} parts, in the sense of Remark 9, whose existence may be ensured, and suppose N_{0} = N_{0}(ε, k_{0}) is such that any graph with n ≥ N_{0} vertices is guaranteed to admit such a partition. Now let K′_{0} = max{K_{0}, N_{0}}, and observe that, then, any graph admits an ε-regular partition into k parts, where k_{0} ≤ k ≤ K′_{0}. Indeed, if the given graph G has fewer than N_{0} vertices, it suffices to consider the partition of V (G) into singletons.

For the sake of completeness, we explicitly state the conclusion of Remarks 9 and 10 as a theorem.

Theorem 11. For any given ε > 0 and k_{0} ≥ 1, there is a constant K_{0} = K_{0}(ε, k_{0}) ≥ k_{0} such that any graph G admits a partition (C_{i})_{1}^{k} of its vertex set such that

(i) k_{0} ≤ k ≤ K_{0}, (ii) ⌊n/k⌋ ≤ |C_{1}| ≤ ⋯ ≤ |C_{k}| ≤ ⌈n/k⌉, and (iii) at least (1 − ε)\binom{k}{2} of the pairs (C_{i}, C_{j}) with 1 ≤ i < j ≤ k are ε-regular.

2.1.2. Irregular pairs and the number of blocks in regular partitions. The notion of an ε-regular partition given in Definition 3 gives us a little breathing room in that it allows up to ε\binom{k}{2} irregular pairs (C_{i}, C_{j}) in a k-equitable partition ⋃_{0≤i≤k} C_{i}. Whether this is required is a rather natural question (already raised by Szemerédi [60]): is there a strengthening of the regularity lemma that guarantees the existence of an (ε, k)-equitable partition with all the \binom{k}{2} pairs ε-regular for any large enough graph?

As observed by several researchers, Lovász, Seymour, Trotter, and the authors of [5] among others (see [5, p. 82]), the irregular pairs are required. A simple example that shows this is as follows: let B = (U, W; E) be the bipartite graph with U = W = [n], and ij ∈ E if and only if i ≤ j. The reader is invited to prove that, for small enough ε > 0, any (ε, k)-equitable, ε-regular partition of this graph requires at least ck ε-irregular pairs, where c = c(ε) > 0 is some constant that depends only on ε.

Let us now turn to the value of the constants K_{0} = K_{0}(ε, k_{0}) and N_{0} = N_{0}(ε, k_{0}) in the statement of the regularity lemma, Theorem 4. As we discussed in Remark 10, the requirement that we should only deal with graphs G = G^{n} with n ≥ N_{0} is not important. However, K_{0} = K_{0}(ε, k_{0}) is much more interesting.

The original proof of Theorem 4 gave for K_{0} a tower of 2s of height proportional to ε^{−5}, which is quite a large constant for any reasonable ε. (How such a number comes about may be seen very clearly in the proof of Theorem 13, given in Section 5.) As proved by Gowers [34], there are graphs for which such a huge number of classes are required in any ε-regular partition. We only give a weak form of the main result in [34] (see Theorem 15 in [34]).

Theorem 12. There exist absolute constants ε_{0} > 0 and c_{0} > 0 for which the following holds. For any 0 < ε ≤ ε_{0}, there is a graph G for which the number of classes in any ε-regular partition of its vertex set must be at least as large as a tower of 2s of height at least c_{0}ε^{−1/16}.

Roughly speaking, the strongest result in [34] states that one may weaken the requirements on the ε-regular partition in certain natural ways and still have the same lower bound as in Theorem 12. The interested reader should study the ingenious probabilistic constructions in [34].

Before we proceed, let us mention again that the readers who are not too familiar with the regularity lemma may at first prefer to skip the next two sections, namely, Sections 2.2 and 2.3, and proceed directly to Section 3, where a typical application of Theorem 4 is discussed in detail.

2.2. A regularity lemma for sparse graphs. We shall now state a version of the regularity lemma for sparse graphs. We in fact consider a slightly more general situation, including the case of ℓ-partite graphs G, where ℓ is some fixed integer.

Let a partition P_{0} = (V_{i})_{1}^{ℓ} (ℓ ≥ 1) of V = V (G) be fixed. For convenience, let us write (U, W) ≺ P_{0} if U ∩ W = ∅ and either ℓ = 1 or else ℓ ≥ 2 and for some i ≠ j (1 ≤ i, j ≤ ℓ) we have U ⊂ V_{i}, W ⊂ V_{j}.

Suppose 0 < η ≤ 1. We say that G is (P_{0}, η)-uniform if, for some 0 < p ≤ 1, we have that for all U, W ⊂ V with (U, W) ≺ P_{0} and |U|, |W | ≥ ηn, we have

|e_{G}(U, W) − p|U||W || ≤ ηp|U||W |.  (11)

As mentioned above, the partition P_{0} is introduced to handle the case of ℓ-partite graphs (ℓ ≥ 2). If ℓ = 1, that is, if the partition P_{0} is trivial, then we are thinking of the case of ordinary graphs. In this case, we shorten the term (P_{0}, η)-uniform to η-uniform.

The prime example of an η-uniform graph is of course a random graph G_{p} = G_{n,p}. For any η > 0 a random graph G_{p} with p = p(n) = C/n is almost surely ηuniform provided C ≥ C_{0} = C_{0}(η), where C_{0}(η) depends only on η. Let 0 < p = p(n) ≤ 1 be given. The standard binomial random graph G_{p} = G_{n,p} has as vertex set a fixed set V (G_{p}) of cardinality n and two such vertices are adjacent in G_{p} with probability p, with all such adjacencies independent. For concepts and results concerning random graphs, see, e.g., Bollobás [13] or Janson, Łuczak, and Ruciński [35]. (A lighter introduction may be Chapter 7 of Bollobás [12, 14].)

We still need to introduce a few further definitions. Let a graph G = G^{n} be fixed as before. Let H ⊂ G be a spanning subgraph of G. For U, W ⊂ V, let

d_{H,G}(U, W) = \{ \begin{matrix}e_{H}(U, W)/e_{G}(U, W) & if e_{G}(U, W) > 0 \\ 0 & if e_{G}(U, W) = 0. \end{matrix}

Suppose ε > 0, U, W ⊂ V, and U ∩ W = ∅. We say that the pair (U, W) is (ε, H, G)-regular, or simply ε-regular, if for all U′ ⊂ U, W′ ⊂ W with |U′| ≥ ε|U| and |W′| ≥ ε|W |, we have

|d_{H,G}(U′, W′) − d_{H,G}(U, W)| ≤ ε.

If P and Q are two equitable partitions of V (see Definition 2 in Section 2.1), we say that Q refines P if every non-exceptional class of Q is contained in some non-exceptional class of P. If P′ is an arbitrary partition of V, then Q refines P′ if every non-exceptional class of Q is contained in some block of P′. Finally, we say that an (ε, k)-equitable partition Q = (C_{i})_{0}^{k} of V is (ε, H, G)-regular, or simply ε-regular, if at most ε\binom{k}{2} pairs (C_{i}, C_{j}) with 1 ≤ i < j ≤ k are not ε-regular. We may now state an extension of Szemerédi’s lemma to subgraphs of (P_{0}, η)-uniform graphs. Theorem 13. Let ε > 0 and k_{0}, ℓ ≥ 1 be fixed. Then there are constants η = η(ε, k_{0}, ℓ) > 0, K_{0} = K_{0}(ε, k_{0}, ℓ) ≥ k_{0}, and N_{0} = N_{0}(ε, k_{0}, ℓ) satisfying the following. For any (P_{0}, η)-uniform graph G = G^{n} with n ≥ N_{0}, where P_{0} = (V_{i})_{1}^{ℓ} is a partition of V = V (G), if H ⊂ G is a spanning subgraph of G, then there exists an (ε, H, G)-regular (ε, k)-equitable partition of V refining P_{0} with k_{0} ≤ k ≤ K_{0}.

Remark 14. To recover the original regularity lemma of Szemerédi from Theorem 13, simply take G = K^{n}, the complete graph on n vertices.

2.3. A second regularity lemma for sparse graphs. In some situations, the sparse graph H to which one would like to apply the regularity lemma is not a subgraph of some fixed η-uniform graph G. A simple variant of Theorem 13 may be useful in this case. For simplicity, we shall not state this variant for ‘P_{0}-partite’ graphs as we did in Section 2.2.

Let a graph H = H^{n} of order |V (H)| = n be fixed. Suppose 0 < η ≤ 1, D ≥ 1, and 0 < p ≤ 1 are given. We say that H is an (η, D)-upper-uniform graph with respect to density p if, for all U, W ⊂ V with U ∩ W = ∅ and |U|, |W | ≥ ηn, we have e_{H}(U, W) ≤ Dp|U||W |. In what follows, for any two disjoint non-empty sets U, W ⊂ V, let the normalized p-density d_{H,p}(U, W) of (U, W) be

d_{H,p}(U, W) = \frac{e_{H}(U, W)}{p|U||W |}.  (12)

Now suppose ε > 0, U, W ⊂ V, and U ∩ W = ∅. We say that the pair (U, W) is (ε, H, p)-regular, or simply (ε, p)-regular, if for all U′ ⊂ U, W′ ⊂ W with |U′| ≥ ε|U| and |W′| ≥ ε|W | we have

|d_{H,p}(U′, W′) − d_{H,p}(U, W)| ≤ ε.

We say that an (ε, k)-equitable partition P = (C_{i})_{0}^{k} of V is (ε, H, p)-regular, or simply (ε, p)-regular, if at most ε\binom{k}{2} pairs (C_{i}, C_{j}) with 1 ≤ i < j ≤ k are not (ε, p)-regular. We may now state a version of Szemerédi’s regularity lemma for (η, D)-upper-uniform graphs. Theorem 15. For any given ε > 0, k_{0} ≥ 1, and D ≥ 1, there are constants η = η(ε, k_{0}, D) > 0, K_{0} = K_{0}(ε, k_{0}, D) ≥ k_{0}, and N_{0} = N_{0}(ε, k_{0}, D) such that any graph H = H^{n} with n ≥ N_{0} vertices that is (η, D)-upper-uniform with respect to density 0 < p ≤ 1 admits an (ε, H, p)-regular (ε, k)-equitable partition of its vertex set with k_{0} ≤ k ≤ K_{0}.

3. An application of the regularity lemma

Here we present an application of the regularity lemma. We believe that this is a fairly illustrative example and we also hope that it will introduce the notion of pseudorandomness in a natural way. We follow certain parts of [55] closely.

3.1. A simple fact about almost all graphs. We start with two definitions. We shall say that a graph G is k-universal if G contains all graphs with k vertices as induced subgraphs. As we shall see below, large graphs are typically k-universal for any small k. Our second definition captures another property of typical graphs, namely, the property that their edges are ‘uniformly distributed’.

Definition 16 (Property R(γ, δ, σ)). We say that a graph G = G^{n} of order n has property R(γ, δ, σ) if, for all S ⊂ V = V (G) with |S| ≥ γn, the number of edges e(S) = e(G[S]) induced by S in G satisfies

e(S) = (σ + O_{1}(δ))\binom{|S|}{2}.  (13)

Let us write G(n, M) for the set of all graphs on the vertex set [n] = {1, …, n} with M edges. Clearly, we have

|G(n, M)| = \binom{\binom{n}{2}}{M}  (14)

for all integers n ≥ 0 and 0 ≤ M ≤ \binom{n}{2}. Let U(n, M; k) be the subset of G(n, M) of all the k-universal graphs, and let R(n, M; γ, δ, σ) be the subset of G(n, M) of all the graphs G ∈ G(n, M) satisfying property R(γ, δ, σ).

The following fact is easy to prove. Fact 17. Let k ≥ 1 be an integer and let 0 < γ ≤ 1, 0 < δ ≤ 1, and 0 < σ < 1 be real numbers. Put M = M(n) = ⌊σ\binom{n}{2}⌋. Then we have

lim_{n→∞} \frac{|U(n, M; k)|}{|G(n, M)|} = 1  (15)

and

lim_{n→∞} \frac{|R(n, M; γ, δ, σ)|}{|G(n, M)|} = 1.  (16)

In the usual language of random graphs, one says that almost all G ∈ G(n, M) are k-universal to mean that (15) holds. Similarly, one says that almost all G ∈ G(n, M) satisfy R(γ, δ, σ) because of (16). If γ and δ are small, the latter assertion may be interpreted to mean that the edges of a typical graph G ∈ G(n, M) are uniformly distributed.

The most direct way to verify Fact 17 is by proving (15) and (16) independently. However, it turns out that, for any deterministic graph G = G^{n}, having property R(γ, δ, σ) for any fixed 0 < σ < 1 implies the k-universality of G. (Of course, the constants γ and δ have to be suitably small with respect to k, and n has to be suitably large with respect to k.) Thus, roughly speaking, having uniformly distributed edges is a stronger property than being universal. (Quite surprisingly, if one strengthens the notion of k-universality to include information on the number of copies of all k-vertex graphs for fixed k ≥ 4, these properties become equivalent in a certain precise sense; see Section 3.2.3 for a short discussion on this point.)

We shall prove that uniform distribution of edges implies universality by making use of the regularity lemma. We shall in fact prove a stronger statement, and we shall see that this statement, coupled with an auxiliary result, confirms a conjecture of Erdős.

3.2. The statement of the results. Let us state the first result we discuss in this section. Theorem 18. For all integers k ≥ 1 and real numbers 0 < σ < 1 and 0 < δ < 1 with δ < σ < 1 − δ, there exist γ > 0 and N_{0} for which the following holds. If G = G^{n} is a graph of order n ≥ N_{0} that satisfies property R(γ, δ, σ), then G is k-universal.

We shall prove Theorem 18 in Section 3.3. It may be worth mentioning that the constant δ, which controls the ‘error’ in (13), is quantified universally in Theorem 18 (under the obviously necessary condition that we should have δ < σ < 1−δ). Thus, the result above tells us that, whatever the magnitude of the error, we may ensure k-universality by requiring control over small enough sets. Somewhat surprisingly, one may also prove a result in which it is the quantity γ that is quantified universally, that is, we are told that we have control over sets of some fixed cardinality, say ⌊n/2⌋, and we would like to guarantee k-universality by requiring a tight enough control over such sets. We make this precise in the following result, proved in [55]. Theorem 19. For all integers k ≥ 1 and real numbers 0 < σ < 1 and 0 < γ < 1, there exist δ > 0 and N_{1} for which the following holds. If G = G^{n} is a graph of order n ≥ N_{1} that satisfies property R(γ, δ, σ), then G is k-universal.

We shall not prove the above result here. We only remark that the proof of Theorem 19 is based on the same tools that are used to prove Theorem 18, but it is a little more delicate. Theorem 19 is closely related to the following result, which was conjectured by Erdős (see [23] or [11, Chapter VI, p. 363]). Theorem 20. For every integer k ≥ 1 and real number 0 < σ < 1, there is an ε > 0 for which the following holds. Suppose a graph G = G^{n} has M = ⌊σ\binom{n}{2}⌋ edges, and for all W ⊂ V = V (G) with |W | = ⌊n/2⌋ we have

e(G[W]) ≥ σ\binom{⌊n/2⌋}{2}(1 − ε).  (17)

Then, if n ≥ n_{0}(k, σ), the graph G contains a K^{k}.

We shall deduce Theorem 20 from Theorem 18 in Section 3.2.1 below. Nikiforov [53] recently proved Theorem 20 by making use of different techniques.

3.2.1. Proof of Theorem 20. Theorem 20 follows from Theorem 18 and the auxiliary claim below. Claim 21. For all real numbers 0 < γ < 1, 0 < δ < 1, and 0 < σ < 1, there is an ε > 0 for which the following holds. Suppose a graph G = G^{n} has M = ⌊σ\binom{n}{2}⌋ edges, and for all W ⊂ V = V (G) with |W | = ⌊n/2⌋ inequality (17) holds. Then, if n ≥ n_{1}(γ, δ, σ), the graph G is such that for all U ⊂ V = V (G) with |U| ≥ γn we have

e(G[U]) ≥ (σ − δ)\binom{|U|}{2}.  (18)

Observe that the conclusion about G in Claim 21 above is very close to property R(γ, δ, σ). Clearly, the difference is that we do not have the upper bound in (13) in Definition 16, which is natural, given the one-sided hypothesis about G in Claim 21. Let us now prove Theorem 20 assuming Theorem 18 and Claim 21.

Proof of Theorem 20. Let k and σ as in the statement of Theorem 20 be given. Put

δ = \frac{1}{2}σ,  (19)

and let

σ′ = \frac{1}{2} ((1 − \frac{1}{k} ) + (σ − δ)) and δ′ = \frac{1}{2} ((1 − \frac{1}{k} ) − (σ − δ)) .  (20)

Clearly, we have

0 < σ′ − δ′ = σ − δ < σ′ + δ′ = 1 − \frac{1}{k} < 1,  (21)

and, in particular, δ′ < σ′ < 1 − δ′. Hence, we may invoke Theorem 18 with k, σ′, and δ′. Theorem 18 then gives us

γ = γ(k, σ′, δ′) and N_{0}(k, σ′, δ′).  (22)

Let us now feed γ, δ, and σ into Claim 21. We obtain

ε = ε(γ, δ, σ) and n_{1}(γ, δ, σ).  (23)

Finally, let n_{0}(k) be such that any graph with n ≥ n_{0}(k) vertices and > (1−1/k)\binom{n}{2} edges must contain a K^{k}. Put

n_{0} = n_{0}(k, σ) = max \{N_{0}(k, σ′, δ′), n_{1}(γ, δ, σ), \frac{1}{γ} n_{0}(k)\} .  (24)

We claim that ε given in (23) and n_{0} given in (24) will do in Theorem 20.

To verify this claim, suppose a graph G = G^{n} with n ≥ n_{0} vertices has M = ⌊σ\binom{n}{2}⌋ edges, and for all W ⊂ V = V (G) with |W | = ⌊n/2⌋ inequality (17) holds. Then, by the choice of ε and n_{0} ≥ n_{1}(γ, δ, σ) (see (23)), we may deduce from Claim 21 that (‡) for all U ⊂ V = V (G) with |U| ≥ γn inequality (18) holds.

Now, since n ≥ n_{0} ≥ γ^{−1}n_{0}(k), we know that if U ⊂ V = V (G) is such that |U| ≥ γn and

e(G[U]) > (1 − \frac{1}{k} ) \binom{|U|}{2},  (25)

then G[U] ⊃ K^{k}. Therefore we may assume that (‡‡) inequality (25) fails for all U ⊂ V = V (G) with |U| ≥ γn.

Assertions (‡) and (‡‡) imply that property R(γ, δ′, σ′) holds for G (see (21)). By the choice of γ and n_{0} ≥ N_{0}(k, σ′, δ′) (see (22)), we may now deduce from Theorem 18 that G is k-universal. This completes the proof of Theorem 20. □

We shall now turn to Claim 21, but before we proceed, we state the following basic fact. Given a set of vertices W ⊂ V (G) with |W | ≥ 2 in a graph G, the edge density d(W) of W is defined to be e(G[W])\binom{|W |}{2}^{−1}. Fact 22. Let G be a graph and suppose we are given W ⊂ V (G) with |W | ≥ 2. Suppose also that 2 ≤ u ≤ |W | is fixed. Then

d(W) = Ave_{U} d(U),  (26)

where the average is taken over all U ⊂ W with |U| = u.

Proof. The one-line proof goes as follows:

Ave_{U} d(U) = \binom{|W |}{u}^{−1} ∑_{U} d(U) = \binom{|W |}{u}^{−1} ∑_{U} e(G[U])\binom{|U|}{2}^{−1}

= e(G[W])\binom{|W |}{u}^{−1}\binom{u}{2}^{−1}\binom{|W | − 2}{u − 2} = e(G[W])\binom{|W |}{2}^{−1}, (27)

where, clearly, the average and the sums are over all U ⊂ W with |U| = u. □

Let us now prove Claim 21.

Proof. Let 0 < γ < 1, 0 < δ < 1, and 0 < σ < 1 be fixed, and suppose that the graph G = G^{n} is as in the statement of the Claim 21. We shall prove that if ε is small enough and n is large enough, then inequality (18) holds for all U ⊂ V = V (G) with |U| ≥ γn.

Observe first that it suffices to consider sets U ⊂ V with |U| = ⌈γn⌉, because of Fact 22. We may also suppose that ⌈γn⌉ < ⌊n/2⌋ and, in fact, 0 < γ < 1/2.

Let U ⊂ V be such that u = |U| = ⌈γn⌉. Put T = V \ U. Let the number of edges between U and T be σ_{1}ut, where t = |T | = n − u. Let also σ_{2}\binom{t}{2} be the number of edges induced by T in G. We have

e(G[U]) + σ_{1}ut + σ_{2}\binom{t}{2} = ⌊σ\binom{n}{2}⌋ .  (28)

Put t′ = ⌊n/2⌋ − u > 0. We now select a t′-element subset T′ of T uniformly at random, and consider the edges that are induced by U ∪ T′. Fix an edge xy of G, with x ∈ U and y ∈ T. Then, xy will be induced by U ∪ T′ if and only if y ∈ T′. However, this happens with probability \binom{t−1}{t′−1}\binom{t}{t′}^{−1} = t′/t. Given that there are σ_{1}ut such edges xy, the expected number of these edges that will be induced by U ∪ T′ is

σ_{1}ut × \frac{t′}{t} = σ_{1}ut′.  (29)

Now fix an edge xy of G with both x and y in T. Then, xy will be induced by U ∪T′ with probability

\binom{t − 2}{t′ − 2}\binom{t}{t′}^{−1} = \frac{t′(t′ − 1)}{t(t − 1)}.  (30)

Since there are σ_{2}\binom{t}{2} such edges xy, the expected number of these edges that will be induced by U ∪ T′ is

σ_{2}\binom{t}{2}\frac{t′(t′ − 1)}{t(t − 1)} = σ_{2}\binom{t′}{2}.  (31)

Therefore, by (29) and (31), the expected number of edges that are induced by U∪T′ is

e(G[U]) + σ_{1}ut′ + σ_{2}\binom{t′}{2}.  (32)

For the remainder of the proof, we fix a set T′ such that this number of induced edges e(G[U ∪T′]) is at least as large as given in (32). Since U ∪T′ is a set with ⌊n/2⌋ vertices, by our hypothesis on G we have

e(G[U]) + σ_{1}ut′ + σ_{2}\binom{t′}{2} ≥ σ\binom{⌊n/2⌋}{2}(1 − ε).  (33)

Subtracting (33) from (28), we obtain

σ_{1}u(t − t′) + σ_{2} (\binom{t}{2} − \binom{t′}{2}) ≤ σ (\binom{n}{2} − (1 − ε)\binom{⌊n/2⌋}{2}) .  (34)

Suppose now that U induces fewer than (σ − δ)\binom{u}{2} edges. Then (33) gives that

(σ − δ)\binom{u}{2} + σ_{1}ut′ + σ_{2}\binom{t′}{2} > σ\binom{⌊n/2⌋}{2}(1 − ε).  (35)

We deduce that

σ_{1}u > \frac{1}{t′} (σ\binom{⌊n/2⌋}{2}(1 − ε) − σ_{2}\binom{t′}{2} − (σ − δ)\binom{u}{2}) .  (36)

Plugging (36) into (34), we obtain

(\frac{t}{t′} − 1) (σ\binom{⌊n/2⌋}{2}(1 − ε) − σ_{2}\binom{t′}{2} − (σ − δ)\binom{u}{2})

+ σ_{2} (\binom{t}{2} − \binom{t′}{2}) < σ (\binom{n}{2} − (1 − ε)\binom{⌊n/2⌋}{2}) . (37)

Observe that t/t′ − 1 → 1/(1 − 2γ) as n → ∞. Therefore, dividing (37) by n^{2} and letting n → ∞, we obtain

\frac{1}{1 − 2γ} (\frac{σ}{8} (1 − ε) − \frac{1}{2}σ_{2} (\frac{1}{2} − γ)^{2} − \frac{1}{2}(σ − δ)γ^{2})

+ \frac{1}{2}σ_{2} (\frac{3}{4} − γ) ≤ \frac{σ}{2} (\frac{1}{2} − \frac{1 − ε}{8}) , (38)

or, rearranging terms,

\begin{aligned}\frac{σ}{8} (1 − ε) + \frac{1}{4}σ_{2}(1 − 2γ)(1 − γ) & − \frac{1}{2}(σ − δ)γ^{2} \\ & ≤ σ (\frac{1}{2} − \frac{1 − ε}{8}) (1 − 2γ). \end{aligned}  (39)

We now observe that Fact 22 and our hypothesis on G implies that σ_{2} ≥ σ(1 − ε). Therefore (39) implies that

\begin{aligned}\frac{σ}{8} (1 − ε) + \frac{1}{4}σ(1 − ε)(1 − 2γ)(1 − γ) & − \frac{1}{2}(σ − δ)γ^{2} \\ & ≤ σ (\frac{1}{2} − \frac{1 − ε}{8}) (1 − 2γ). \end{aligned}  (40)

Letting ε → 0 in (40), we obtain

\frac{σ}{8} + \frac{1}{4}σ(1 − 2γ)(1 − γ) − \frac{1}{2}(σ − δ)γ^{2} ≤ \frac{3}{8}σ(1 − 2γ).  (41)

However, inequality (41) reduces to

\frac{1}{2}δγ^{2} ≤ 0,  (42)

which does not hold. Therefore, there is an ε_{0} = ε_{0}(γ, δ, σ) > 0 such that (40) fails for all 0 < ε ≤ ε_{0}. Moreover, there is n_{0} = n_{0}(γ, δ, σ) ≥ 1 such that (37) fails for all n ≥ n_{0}. However, this implies that if 0 < ε ≤ ε_{0} and n ≥ n_{0}, then U induces at least than (σ−δ)\binom{u}{2} edges. We have thus found ε_{0} = ε_{0}(γ, δ, σ) and n_{0} = n_{0}(γ, δ, σ) as required, and Claim 21 is proved. □

3.2.2. An application in Ramsey theory. Before we proceed to the proof of Theorem 18, we state a pleasant corollary to that result. Let G and H_{1}, …, H_{r} be graphs. We write

G⟶^{ind}(H_{1}, …, H_{r})  (43)

to mean that, however we colour the edges of G with colours c_{1}, …, c_{r}, there must be some i such that G contains an induced subgraph H′ isomorphic to H_{i} and with all its edges coloured with colour c_{i}. Theorem 23. For any collection of graphs H_{1}, …, H_{r}, there is a graph G for which (43) holds.

Theorem 23 was independently proved by Deuber [18], Erdős, Hajnal, and Pósa [21], and Rödl [54]. We leave it as an exercise for the reader to deduce from Theorem 18 that, in fact, almost all graphs G ∈ G(n, M) satisfy (43) if M = ⌊σ\binom{n}{2}⌋, where 0 < σ < 1 is any fixed constant (see [52]).

3.2.3. Uniform edge distribution and subgraph frequency. The proof of Theorem 18 given below may be adapted to prove the following result: for any ε > 0 and 0 < σ < 1, and any integer k ≥ 1, there is a δ > 0 such that if G = G^{n} satisfies property R(δ, δ, σ), then, as long as n ≥ n_{0}(ε, σ, k), (*) for any graph H = H^{k} on k vertices, the number of induced embeddings f: V (H) → V (G) of H in G is

(1 + O_{1}(ε))(n)_{k}σ^{e(H)}(1 − σ)^{\binom{k}{2}−e(H)}.  (44)

As customary, above we write (a)_{b} for a(a − 1) … (a − b + 1). It is straightforward that the expected number of embeddings f as above in the random graph G ∈ G(n, M) is given by (44), where M = M(n) = ⌊σ\binom{n}{2}⌋, and in fact the number of such embeddings is this number for almost all G ∈ G(n, M). Thus, again, the deterministic property R(δ, δ, σ) captures a feature of random graphs. Surprisingly, this ‘numerical’ version of k-universality for k = 4, that is, property (*) for k = 4, implies property R(δ, δ, σ), as long as ε is small enough with respect to δ and σ.

The properties above, together with several others, are now known as quasirandom graph properties. The interested reader is referred to Thomason [62, 63], Frankl, Rödl, and Wilson [26], and Chung, Graham, and Wilson [15] (see also Alon and Spencer [8, Chapter 9]). The study of quasi-randomness is appealing in its own right, but one may perhaps argue that investigating quasi-randomness for graphs is especially important because of the intimate relation between quasi-randomness, ε-regularity, and the regularity lemma.

In Section 7, we shall introduce a new quasi-random property for graphs.

3.3. The proof of Theorem 18. The proof of Theorem 18 is based on the regularity lemma, Theorem 4, and on an embedding lemma, which asserts the existence of certain embeddings of graphs.

In this proof, γ, δ, σ, ε, β, and ε_{k} will always denote positive constants smaller than 1.

3.3.1. The embedding lemma. We start with a warm-up. Suppose we have a tripartite graph G = G^{3ℓ}, with tripartition V (G) = B_{1} ∪ B_{2} ∪ B_{3}, where |B_{1}| = |B_{2}| = |B_{3}| = ℓ > 0. Suppose also that all the 3 pairs (B_{i}, B_{j}), 1 ≤ i < j ≤ 3, are ε-regular, with d(B_{i}, B_{j}) = σ > 0 for all 1 ≤ i < j ≤ 3.

We claim that, then, the graph G contains a triangle provided ε is small with respect to σ. To prove this claim, first observe that, from the ε-regularity of (B_{1}, B_{2}) and of (B_{1}, B_{3}), one may deduce that there are at least (1 − 4ε)ℓ > 0 vertices b_{1} in B_{1} such that their degrees into B_{2} and B_{3} are both at least (σ − ε)ℓ and at most (σ + ε)ℓ (see Claim 27 below). However, by the ε-regularity of (B_{2}, B_{3}), at least

(σ − ε)|Γ(b_{1}) ∩ B_{2}||Γ(b_{1}) ∩ B_{3}| ≥ (σ − ε)^{3}ℓ^{2} > 0  (45)

edges are induced by the pair (Γ(b_{1}) ∩ B_{2}, Γ(b_{1}) ∩ B_{3}) as long as σ − ε ≥ ε, that is, ε < σ/2. Thus the claim is proved. Note that, in fact, we have proved that if ε < σ/2, then the number of triangles in G is at least

cℓ^{3} = c(σ, ε)ℓ^{3},  (46)

where c(σ, ε) = (1 − 4ε)(σ − ε)^{3}. Clearly, c(σ, ε) → σ^{3} as ε → 0. For comparison, let us observe that the number of triangles is ∼ σ^{3}ℓ^{3} as ℓ → ∞ if G is drawn at random from all the tripartite graphs on (B_{1}, B_{2}, B_{3}) with ⌊σℓ^{2}⌋ edges within all the pairs (B_{i}, B_{j}).

Let us now turn to the embedding lemma that we shall use to prove Theorem 18. We have already seen the essence of the proof of this lemma in the warm-up above. In order to state the lemma concisely, we introduce the following definition.

Definition 24 (Property P(k, ℓ, β, ε)). A graph G has property P(k, ℓ, β, ε) if it admits a partition V = V (G) = ⋃_{1≤i≤k} B_{i} of its vertex set such that

(i) |B_{i}| = ℓ for all 1 ≤ i ≤ k, (ii) all the \binom{k}{2} pairs (B_{i}, B_{j}), where 1 ≤ i < j ≤ k, are ε-regular, and (iii) β < d(B_{i}, B_{j}) < 1 − β for all 1 ≤ i < j ≤ k.

The embedding lemma is as follows. Lemma 25. For all 0 < β < 1/2 and k ≥ 1, there exist ε_{k} = ε_{k}(k, β) > 0 and ℓ_{k} = ℓ_{k}(k, β) so that every graph with property P(k, ℓ, β, ε_{k}) with ℓ ≥ ℓ_{k} is k-universal.

Remark 26. If H is some graph on k vertices and G is a graph satisfying property P(k, ℓ, β, ε_{k}), then one may in fact estimate the number of copies of H in G (cf. (46)). Variants of Lemma 25 that give such numerical information are sometimes referred to as counting lemmas.

Before we start the proof of Lemma 25, we state and prove a simple claim on regular pairs. If u is a vertex in a graph G and W ⊂ V (G), then we write d_{W} (u) for the degree |Γ(u) ∩ W | of u ‘into’ W. Claim 27. Let (U, W) be an ε-regular pair in a graph G, and suppose d(U, W) = ϱ. Then the number of vertices u ∈ U satisfying

(ϱ − ε)|W | ≤ d_{W} (u) = |Γ(u) ∩ W | ≤ (ϱ + ε)|W |  (47)

is more than (1 − 2ε)|U|.

Proof. Suppose for a contradiction that Claim 27 is false. Let U^{−} ⊂ U be the set of u ∈ U for which the first inequality in (47) fails, and let U^{+} ⊂ U be the set of u ∈ U for which the second inequality in (47) fails. We are assuming that |U^{+} ∪ U^{−}| ≥ 2ε|U|. Therefore, say, |U^{+}| ≥ ε|U|. However, we then have

d(U^{+}, W) > ϱ + ε.  (48)

Since (U, W) is ε-regular, such a witness of ε-irregularity cannot exist. The case in which |U^{−}| ≥ ε|U| is similar. This proves Claim 27. □

We now give the proof of the embedding lemma, Lemma 25.

Proof of Lemma 25. The proof will be by induction on k. For k = 1 the statement of the lemma is trivial. For k = 2, it suffices to take ε_{2} = ε_{2}(2, β) = β and ℓ_{2}(2, β) = 1. Indeed, observe that the fact that 0 < d(B_{1}, B_{2}) < 1 implies that there must be b_{i} and b′_{i} ∈ B_{i} (i ∈ {1, 2}) such that b_{1}b_{2} is an edge and b′_{1}b′_{2} is not an edge. For the induction step, suppose that k ≥ 3 and that the assertion of the lemma is true for smaller values of k and for all 0 < β < 1/2.

Suppose we are given some β, with 0 < β < 1/2. Let

ε_{k} = ε_{k}(k, β) = min \{\frac{1}{2k} , \frac{1}{2}βε_{k−1}\} ,  (49)

and

ℓ_{k} = ℓ_{k}(k, β) = max \{2 ⌈\frac{ℓ_{k−1}}{β} ⌉ , k\} ,  (50)

where

ε_{k−1} = ε_{k−1}(k − 1, β/2) and ℓ_{k−1} = ℓ_{k−1}(k − 1, β/2).  (51)

We claim that the choices for ε_{k} and ℓ_{k} in (49) and (50) will do. Thus, let G be a graph satisfying property P(k, ℓ, β, ε_{k}), where ℓ ≥ ℓ_{k}. Let B_{1}, …, B_{k} be the blocks of the partition of V = V (G) ensured by Definition 24. Suppose H is a graph on the vertices x_{1}, …, x_{k}. We shall show that there exist b_{1}, …, b_{k}, with b_{i} ∈ B_{i}, such that the map ϕ: x_{i} ↦ b_{i} is an embedding of H into G (that is, ϕ is an isomorphism between H and G[b_{1}, …, b_{k}], the graph induced by the b_{i} in G).

Pick a vertex b_{k} ∈ B_{k} for which

(d(B_{k}, B_{j}) − ε_{k})ℓ < d_{B_{j}}(b_{k}) = |Γ(b_{k}) ∩ B_{j}| < (d(B_{k}, B_{j}) + ε_{k})ℓ  (52)

for all 1 ≤ j < k. The existence of such a vertex b_{k} follows from Claim 27. Indeed, the claim tells us that the number of vertices that fail (52) for some 1 ≤ j < k is at most

2(k − 1)ε_{k}ℓ < ℓ = |B_{k}|,  (53)

since ε_{k} ≤ 1/2k (see (49)). For all 1 ≤ j < k, we now choose sets B̃_{j} ⊂ B_{j} satisfying the following properties:

(i) |B̃_{j}| = ⌈βℓ/2⌉ ≥ ℓ_{k−1}, (ii) if x_{j}x_{k} ∈ E(H), then bb_{k} ∈ E(G) for all b ∈ B̃_{j}, and if x_{j}x_{k} ∉ E(H),

then bb_{k} ∉ E(G) for all b ∈ B̃_{j}.

The existence of the sets B̃_{j} (1 ≤ j < k) follows from our choice of b_{k}. Indeed,

(52) tells us that b_{k} has more than

(d(B_{k}, B_{j}) − ε_{k})ℓ > (β − ε_{k})ℓ ≥ (β − \frac{1}{2}βε_{k−1}) ℓ ≥ \frac{1}{2}βℓ  (54)

neighbours in B_{j}. Similarly, (52) tells us that b_{k} has more than

(1 − d(B_{k}, B_{j}) − ε_{k})ℓ > (β − ε_{k})ℓ ≥ \frac{1}{2}βℓ  (55)

non-neighbours in B_{j}.

Now fix a pair 1 ≤ i < j < k, and let X_{i} ⊂ B̃_{i} and X_{j} ⊂ B̃_{j} be such that |X_{i}| ≥ ε_{k−1}|B̃_{i}| and |X_{j}| ≥ ε_{k−1}|B̃_{j}|. Then

min\{|X_{i}|, |X_{j}|\} ≥ ε_{k−1}|B̃_{i}| = ε_{k−1}|B̃_{j}| ≥ \frac{2ε_{k}}{β} ⌈\frac{βℓ}{2}⌉ ≥ ε_{k}ℓ.  (56)

From the ε_{k}-regularity of the pair (B_{i}, B_{j}), we deduce that

|d(X_{i}, X_{j}) − d(B̃_{i}, B̃_{j})|

≤ |d(X_{i}, X_{j}) − d(B_{i}, B_{j})| + |d(B_{i}, B_{j}) − d(B̃_{i}, B̃_{j})| ≤ 2ε_{k} ≤ ε_{k−1}. (57)

Therefore all the pairs (B̃_{i}, B̃_{j}) with 1 ≤ i < j < k are ε_{k−1}-regular. Our induction hypothesis then tells us that there exist b_{j} ∈ B_{j} (1 ≤ j < k) for which the map x_{j} ↦ b_{j} (1 ≤ j < k) is an isomorphism between H − x_{k} and G[b_{1}, …, b_{k−1}]. Clearly, ϕ: x_{j} ↦ b_{j} (1 ≤ j ≤ k) is an isomorphism between H and G[b_{1}, …, b_{k}]. □

3.3.2. Proof of Theorem 18. We are now able to prove Theorem 18. We shall make use of two well known results from graph theory: Ramsey’s theorem and Turán’s theorem.

Proof of Theorem 18. Let δ_{1} = max{σ + δ − 1/2, 1/2 − σ + δ}. We clearly have 0 < δ_{1} < 1/2 and in fact

\begin{aligned}0 < \frac{1}{2} − δ_{1} & ≤ \frac{1}{2} − (\frac{1}{2} − σ + δ) \\ & = σ − δ ≤ σ + δ = \frac{1}{2} + (σ + δ − \frac{1}{2}) ≤ \frac{1}{2} + δ_{1} < 1. \end{aligned}  (58)

The inequalities in (58) imply that property R(γ, δ, σ) implies property R(γ, δ_{1}, 1/2). Therefore we may assume in Theorem 18 that σ = 1/2 and 0 < δ < 1/2. We may further assume that

k ≥ \frac{3}{β} , where β = \frac{1}{2} − δ > 0.  (59)

We now define the constants γ and N_{0} promised in Theorem 18. Put

ε = min \{\frac{1}{R(k, k, k)}, ε_{k}\} ,  (60)

where ε_{k} = ε_{k}(k, β/2) is the number whose existence is guaranteed by Lemma 25, and R(k, k, k) is the usual Ramsey number for K^{k} and three colours: R(k, k, k) is the minimal integer R such that, in any colouring of the edges of K^{R} with three colours, we must have a K^{k} all of whose edges are coloured with the same colour.

Put k_{0} = R(k, k, k), and invoke Theorem 4 with this k_{0} and ε given in (60). We obtain constants K_{0}(ε, k_{0}) ≥ k_{0} and N_{0}(ε, k_{0}). Now let

N_{0} = max \{N_{0}(ε, k_{0}), \frac{1}{1 − ε}K_{0}(ε, k_{0})ℓ_{k}\} ,  (61)

where ℓ_{k} = ℓ_{k}(k, β/2) is given by Lemma 25. Furthermore, we let

γ = \frac{k(1 − ε)}{K_{0}(ε, k_{0})}.  (62)

Our aim is to show that the choices for N_{0} and γ given in (61) and (62) will do.

Suppose a graph G = G^{n} with n ≥ N_{0} vertices satisfies property R(γ, δ, 1/2). We shall use the regularity lemma to find an induced subgraph G′ of G that satisfies property P(k, ℓ, β/2, ε_{k}), where ℓ ≥ ℓ_{k}. An application of the embedding lemma, Lemma 25, will then complete the proof.

Let V = V (G) = ⋃_{0≤i≤t} C_{i} be an ε-regular, (ε, t)-equitable partition for G with k_{0} ≤ t ≤ K_{0}(ε, k_{0}). The existence of such a partition is ensured by Theorem 4. Let ℓ = |C_{i}| (1 ≤ i ≤ t).

Consider the graph F on the vertex set [t] = {1, …, t}, where ij ∈ E(F) if and only if (C_{i}, C_{j}) is an ε-regular pair in G. We know that F has at least (1 − ε)\binom{t}{2} edges. By the well-known theorem of Turán [64], it follows that F has a clique with R = R(k, k, k) vertices. Adjust the notation so that this clique is induced by the vertices 1, …, R. Then the blocks C_{i} (1 ≤ i ≤ R) are such that all the pairs (C_{i}, C_{j}) with 1 ≤ i < j ≤ R are ε-regular.

We now define a partition T_{1} ∪T_{2} ∪T_{3} of the set \binom{[R]}{2} of the pairs ij (1 ≤ i < j ≤ R) as follows: the pair ij belongs to T_{1} if and only if d(C_{i}, C_{j}) ≤ β/2; the pair ij belongs to T_{2} if and only if β/2 < d(C_{i}, C_{j}) < 1 − β/2; and, finally, the pair ij belongs to T_{3} if and only if d(C_{i}, C_{j}) ≥ 1 − β/2.

By the definition of R = R(k, k, k), we know that there is a set J ⊂ [R] with |J| = k such that F [J] is monochromatic, that is, \binom{J}{2} ⊂ T_{α} for some α ∈ \{1, 2, 3\}. We consider the graph

G′ = G[ ⋃_{j∈J} C_{j}]  (63)

induced by ⋃_{j∈J} C_{j} in G. Suppose α = 1. Then the number of edges e(G′) in G′ satisfies

e(G′) ≤ \binom{k}{2}\frac{β}{2} ℓ^{2} + k\binom{ℓ}{2} ≤ \frac{βk^{2}ℓ^{2}}{4} + \frac{kℓ^{2}}{2} < (\frac{1}{2} − δ) \binom{kℓ}{2},  (64)

where we have used (59) and the fact that kℓ ≥ k > 6. Since |V (G′)| = kℓ ≥ (1 − ε)kn/K_{0}(ε, k_{0}) = γn (see (62)), inequality (64) contradicts property P(γ, δ, 1/2). This contradiction shows that α ≠ 1. If α = 3, then we obtain a similar contradiction. In this case, as a little calculation using (59) shows, the graph G′ satisfies

e(G′) ≥ \binom{k}{2} (1 − \frac{β}{2} ) ℓ^{2} > (\frac{1}{2} + δ) \binom{kℓ}{2}.  (65)

Thus α ≠ 3 and we conclude that α = 2. We finally observe that, by (61), we have

ℓ ≥ \frac{(1 − ε)n}{K_{0}(ε, k_{0})} ≥ \frac{(1 − ε)N_{0}}{K_{0}(ε, k_{0})} ≥ ℓ_{k}.  (66)

Therefore, as promised, the graph G′ satisfies property P(k, ℓ, β/2, ε_{k}) for ℓ ≥ ℓ_{k}. To complete the induction step, it suffices to invoke Lemma 25.

The proof of Theorem 18 is complete. □

4. Further applications

In this section, we mention a few more applications of the regularity lemma to illustrate some further aspects of its uses.

4.1. Embedding large bounded degree graphs. Lemma 25, the embedding lemma, deals with induced embedding, that is, there we are concerned with embedding certain graphs as induced subgraphs in a given graph. In several applications, one is interested in finding embeddings as subgraphs that need not be necessarily induced. In this section, we shall briefly discuss some variants of Lemma 25 for ‘non-induced’ embeddings.

Let us say that a graph G has property P_{w}(k, ℓ, β, ε) if it satisfies the conditions in Definition 24, except that, instead of (iii) in that definition, we only require the following weaker property:

(iv) d(B_{i}, B_{j}) > β for all 1 ≤ i < j ≤ k. We now state a variant of the embedding lemma for subgraphs; at the expense of requiring that the graph to be embedded should have bounded degree, we gain on the size of the graph that we are able to embed. For convenience, let us say that a graph H is of type (m, k) if H admits a proper vertex colouring with k colours in such a way that every colour occurs at most m times.

Lemma 28. For all k ≥ 1, β > 0 and Δ ≥ 1, there exist ε = ε(k, β, Δ) > 0, ν = ν(k, β, Δ) > 0, and ℓ_{0} = ℓ_{0}(k, β, Δ) so that every graph with property P_{w}(k, ℓ, β, ε) with ℓ ≥ ℓ_{0} contains all graphs of type (νℓ, k) that have maximum degree at most Δ.

Let us stress that the lemma above allows us to embed bounded degree graphs H = H^{n} in certain graphs G = G^{N} with N only linearly larger than n. The regularity lemma and Lemma 28 were the key tools in Chvátal, Rödl, Szemerédi, and Trotter [16], where it is proved that the Ramsey number of a bounded degree graph H = H^{n} is linear in n.

The proof of Lemma 28 in [16] gives for ν an exponentially small quantity in Δ. Thus, one has to have ‘a lot of extra room’ for the embedding. A recent, beautiful result of Komlós, Sárközy, and Szemerédi [45] (see [46] for an algorithmic version), known as the blow-up lemma, shows that one need not waste so much room; in fact, one does not have to waste any room at all if a small extra hypothesis is imposed on the graph where the embedding is to take place.

Let (U, W) be an ε-regular pair in a graph G. We say that (U, W) is (ε, δ)-super-regular if

(†) for all u ∈ U, we have d(u) ≥ δ|W |, and for all w ∈ W, we have d(w) ≥ δ|U|.

Observe that (†) implies that d(U, W) ≥ δ. Let us say that a graph G satisfies property P_{w}(k, ℓ, β, ε, δ) if it satisfies P_{w}(k, ℓ, β, ε), with (ii) in the definition of property P(k, ℓ, β, ε), Definition 24, strengthened to

(v) all the \binom{k}{2} pairs (B_{i}, B_{j}), where 1 ≤ i < j ≤ k, are (ε, δ)-super-regular.

We may now state the blow-up lemma.

Theorem 29. For all k ≥ 1, β > 0, δ > 0, and Δ ≥ 1, there exist ε = ε(k, β, δ, Δ) > 0 and ℓ_{0} = ℓ_{0}(k, β, δ, Δ) so that every graph that satisfies property P_{w}(k, ℓ, β, ε, δ) with ℓ ≥ ℓ_{0} contains all graphs of type (ℓ, k) that have maximum degree at most Δ.

The striking difference between Lemma 28 and Theorem 29 is that, with the rather weak additional condition (†), we are able to embed spanning subgraphs (that is, we may take ν = 1).

Theorem 29 is one of the key ingredients in the recent successes of Komlós, Sárközy, and Szemerédi in tackling well-known, hard conjectures such as Seymour’s conjecture and Pósa’s conjecture on powers of Hamiltonian cycles [47, 48], a conjecture of Bollobás on graph packings [44], and Alon and Yuster’s conjecture [9] (see [43, p. 175]).

We shall not discuss the proof of Theorem 29, which is indeed quite difficult (see [56, 57] for alternative proofs). The reader should consult Komlós [43] for a survey on the blow-up lemma.

4.2. Property testing. We shall now discuss a recent application of regularity to a complexity problem. We shall see how the regularity lemma may be used to prove the correctness of certain algorithms. This section is based on results due to Alon, Fischer, Krivelevich, and Szegedy [6, 7]. These authors develop a new variant of the regularity lemma and use it to prove a far reaching result concerning the testability of certain graph properties.

As a starting point, we state the following result, which the reader should first try to prove with bare hands.

Theorem 30. For any ε > 0 there is a δ > 0 for which the following holds. Suppose a graph G = G^{n} = (V, E) is such that G − F = (V, E \ F) contains a triangle for any set F ⊂ \binom{V}{2} with |F | ≤ ε\binom{n}{2}. Then G contains at least δn^{3} triangles.

The theorem above follows easily from the warm-up result in Section 3.3.1 and the regularity lemma. A proof of Theorem 30 that does not use the regularity lemma (in any form!) would be of considerable interest.

Theorem 30 implies that we may efficiently distinguish triangle-free graphs from graphs that contain triangles in a robust way, that is, graphs G as in the statement of this theorem. Indeed, one may simply randomly pick a number of vertices, say N, from the input graph G = G^{n} and then check whether a triangle is induced. If we catch no triangle, we return the answer ‘yes, the graph G is triangle-free’. If we do catch a triangle, we return the answer ‘no, the graph G is “ε-far” from being triangle-free’.

The striking fact about the algorithm above is that it will return the correct answer with high probability if N is a large enough constant with respect to ε. Here, N need not grow with n, the number of vertices in the input graph G = G^{n}, and hence this is a constant time algorithm. In this section, we shall briefly discuss some far reaching generalizations of this result.

4.2.1. Definitions and the testability result. The general notion of property testing was introduced by Rubinfeld and Sudan [58], but in the context of combinatorial testing it is the work of Goldreich and his co-authors [29, 30, 31, 32, 33] that are most relevant to us.

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

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

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

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

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

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

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

We are now ready to turn to the result of Alon, Fischer, Krivelevich, and Szegedy [6, 7]. Let us consider properties from the first order theory of graphs. Thus, we are concerned with properties that may be expressed through quantification of vertices, Boolean connectives, equality, and adjacency. Of particular interest are the properties that may be expressed in the form

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

where A is a quantifier-free first order expression. Let us call such properties of type ∃∀. Similarly, we define properties of type ∀∃. The main result of [6, 7] is as follows. Theorem 31. All first order properties of graphs that may be expressed with at most one quantifier as well as all properties that are of type ∃∀ are testable. Furthermore, there exist first order properties of type ∀∃ that are not testable.

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

4.2.2. A variant of the regularity lemma. In this section we shall state a variant of the regularity lemma proved in [6, 7].

Let us say that a partition P = (C_{i})_{i=1}^{k} of a set V is an equipartition of V if all the sets C_{i} (1 ≤ i ≤ k) differ by at most 1 in size. In this section, we shall be interested in partitions as in Remark 9 and Theorem 11. Below, we shall have an equipartition of V

P′ = {C_{i,j}: 1 ≤ i ≤ k, 1 ≤ j ≤ ℓ}

that is a refinement of a given partition P = (C_{i})_{i=1}^{k}. In this notation, we understand that, for all i, all the C_{i,j} (1 ≤ j ≤ ℓ) are contained in C_{i}. Theorem 32. For every integer k_{0} and every function 0 < ε(r) < 1 defined on the positive integers, there are constants K = K(k_{0}, ε) and N = N(k_{0}, ε) with the following property. If G is any graph with at least N vertices, then there exist equipartitions P = (C_{i})_{1≤i≤k} and P′ = (C_{i,j})_{1≤i≤k, 1≤j≤ℓ} of V = V (G) such that the following hold:

(i) |P | = k ≥ k_{0} and |P′| = kℓ ≤ K; (ii) at least (1 − ε(0))\binom{k}{2} of the pairs (C_{i}, C_{i′}) with 1 ≤ i < i′ ≤ k are ε(0)-

regular; (iii) for all 1 ≤ i < i′ ≤ k, at least (1 − ε(k))ℓ^{2} of the pairs (C_{i,j}, C_{i′,j′}) with j,

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

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

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

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

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

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

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

Roughly speaking, this consequence of Theorem 32 lets us have some grip on the irregular pairs. Even if (C_{i}, C_{i′}) is irregular, the pair (C_{i,j(i)}, C_{i′,j(i′)}) is regular and hence we have some control over the induced bipartite graph G[C_{i}, C_{i′}]. For instance, if in some application we have to construct some bipartite graph within G[C_{i}, C_{i′}], we may do so by working on the subgraph G[C_{i,j(i)}, C_{i′,j(i′)}].

We have already observed that we must allow irregular pairs in Theorem 4 (see Section 2.1.2). In a way, Theorem 32 presents a way around this difficulty.

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

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

The case in which H is a complete graph follows from the original regularity lemma (the warm-up observation of Section 3.3.1 proved this for H = K^{3}), but the general case requires the corollary to Theorem 32 discussed above. Note that Theorem 33 immediately implies that the property of membership in Forb_{ind}(H) (in order words, the property of not containing an induced copy of H) is a testable property for any graph H.

The proof of Theorem 31 requires a generalization of Theorem 33 related to the colouring problem alluded to at the end of Section 4.2.1. We refer the reader to [6, 7]. We close by remarking that Theorem 32 has an algorithmic version, although we stress that this is not required in the proof of Theorem 31.

5. Proof of the regularity lemma

We now prove the regularity lemma for sparse graphs. We shall prove Theorem 13. The proof of Theorem 15 is similar. We observe that the proof below follows very closely the proof of the original regularity lemma, Theorem 4. Indeed, to recover a proof of Theorem 4 from the proof below, it suffices to set G = K^{n}.

5.1. The refining procedure. Fix G = G^{n} and put V = V (G). Also, assume that P_{0} = (V_{i})_{1}^{ℓ} is a fixed partition of V, and that G is (P_{0}, η)-uniform for some 0 < η ≤ 1. Moreover, let p = p(G) be as in (11).

We start with a ‘continuity’ result. Let H ⊂ G be a spanning subgraph of G.

Lemma 34. Let 0 < δ ≤ 10^{−2} be fixed. Let U, W ⊂ V (G) be such that (U, W) ≺ P_{0}, and δ|U|, δ|W | ≥ ηn. If U^{∗} ⊂ U, W^{∗} ⊂ W, |U^{∗}| ≥ (1 − δ)|U|, and |W^{∗}| ≥ (1 − δ)|W |, then

(i) |d_{H,G}(U^{∗}, W^{∗}) − d_{H,G}(U, W)| ≤ 5δ, (ii) |d_{H,G}(U^{∗}, W^{∗})^{2} − d_{H,G}(U, W)^{2}| ≤ 9δ.

Proof. Note first that we have η ≤ δ, as ηn ≤ δ|U|, δ|W | ≤ δn. Let U^{∗}, W^{∗} be as given in the lemma. We first check (i).

(i) We start by noticing that

d_{H,G}(U^{∗}, W^{∗}) ≥ \frac{e_{H}(U, W) − 2(1 + η)pδ|U||W |}{e_{G}(U, W)}

≥ d_{H,G}(U, W) − 2δ \frac{1 + η}{1 − η} ≥ d_{H,G}(U, W) − 3δ.

Moreover,

d_{H,G}(U^{∗}, W^{∗}) ≤ \frac{e_{H}(U, W)}{e_{G}(U^{∗}, W^{∗})} ≤ \frac{e_{H}(U, W)}{(1 − η)p|U^{∗}||W^{∗}|}

≤ \frac{e_{H}(U, W)}{(1 − η)p(1 − δ)^{2}|U||W |} ≤ \frac{1 + η}{(1 − η)(1 − δ)^{2}} d_{H,G}(U, W)

≤ d_{H,G}(U, W) + 5δ.

Thus (i) follows.

(ii) The argument here is similar. First

d_{H,G}(U^{∗}, W^{∗}) ≥ \frac{(e_{H}(U, W) − 2(1 + η)pδ|U||W |)^{2}}{e_{G}(U, W)^{2}}

≥ d_{H,G}(U, W)^{2} − \frac{4(1 + η)pδ|U||W |e_{H}(U, W)}{e_{G}(U, W)(1 − η)p|U||W |}

≥ d_{H,G}(U, W)^{2} − 4δ \frac{1 + δ}{1 − δ} ≥ d_{H,G}(U, W)^{2} − 5δ.

Secondly,

d_{H,G}(U^{∗}, W^{∗})^{2} ≤ \frac{e_{H}(U, W)^{2}}{e_{G}(U^{∗}, W^{∗})^{2}}

≤ \frac{e_{H}(U, W)^{2}}{(1 − η)^{2}p^{2}|U^{∗}|^{2}|W^{∗}|^{2}} ≤ \frac{e_{H}(U, W)^{2}}{(1 − η)^{2}(1 − δ)^{4}p^{2}|U||W |}

≤ (\frac{1 + η}{(1 − η)(1 − δ)^{2}} )^{2} d_{H,G}(U, W)^{2} ≤ d_{H,G}(U, W)^{2} + 9δ.

Thus (ii) follows. □

In what follows, a constant 0 < ε ≤ 1/2 and a spanning subgraph H ⊂ G of G is fixed. Also, we let P = (C_{i})_{0}^{k} be an (ε, k)-equitable partition of V = V (G) refining P_{0}, where 4^{k} ≥ ε^{−5}. Moreover, we assume that η ≤ η_{0} = η_{0}(k) = 1/k4^{k+1} and that n = |G| ≥ n_{0} = n_{0}(k) = k4^{1+2k}.

We now define an equitable partition Q = Q(P) of V = V (G) from P as follows. First, for each (ε, H, G)-irregular pair (C_{s}, C_{t}) of P with 1 ≤ s < t ≤ k, we choose X = X(s, t) ⊂ C_{s}, Y = Y (s, t) ⊂ C_{t} such that (i) |X|, |Y | ≥ ε|C_{s}| = ε|C_{t}|, and (ii) |d_{H,G}(X, Y) − d_{H,G}(C_{s}, C_{t})| ≥ ε. For fixed 1 ≤ s ≤ k, the sets X(s, t) in

{X = X(s, t) ⊂ C_{s} : 1 ≤ t ≤ k and (C_{s}, C_{t}) is not (ε, H, G)-regular}

define a natural partition of C_{s} into at most 2^{k−1} blocks. Let us call such blocks the atoms of C_{s}. Now let q = 4^{k} and set m = ⌊|C_{s}|/q⌋ (1 ≤ s ≤ k). Note that ⌊|C_{s}|/m⌋ = q as |C_{s}| ≥ n/2k ≥ 2q^{2}. Moreover, for later use, note that m ≥ ηn. We now let Q′ be a partition of V = V (G) refining P such that (i) C_{0} is a block of Q′, (ii) all other blocks of Q′ have cardinality m, except for possibly one, which has cardinality at most m − 1, (iii) for all 1 ≤ s ≤ k, every atom A ⊂ C_{s} contains exactly ⌊|A|/m⌋ blocks of Q′, (iv) for all 1 ≤ s ≤ k, the set C_{s} contains exactly q = ⌊|C_{s}|/m⌋ blocks of Q′.

Let C′_{0} be the union of the blocks of Q′ that are not contained in any class C_{s} (1 ≤ s ≤ k), and let C′_{i} (1 ≤ i ≤ k′) be the remaining blocks of Q′. We are finally ready to define our equitable partition Q = Q(P): we let Q = (C′_{i})_{1}^{k′}. Lemma 35. The partition Q = Q(P) = (C′_{i})_{0}^{k′} defined from P as above is a k′- equitable partition of V = V (G) refining P, where k′ = kq = k4^{k}, and |C′_{0}| ≤ |C_{0}| + n4^{−k}.

Proof. Clearly Q refines P. Moreover, clearly m = |C′_{1}| = … = |C′_{k′}| and, for all 1 ≤ s ≤ k, we have |C′_{0}| ≤ |C_{0}| + k(m − 1) ≤ |C_{0}| + k|C_{s}|/q ≤ |C_{0}| + n4^{−k}. □

In what follows, for 1 ≤ s ≤ k, we let C_{s}(i) (1 ≤ i ≤ q) be the classes of Q′ that are contained in the class C_{s} of P. Also, for all 1 ≤ s ≤ k, we set C_{s}^{∗} = ⋃_{1≤i≤q} C_{s}(i). Now let 1 ≤ s ≤ k be fixed. Note that |C_{s}^{∗}| ≥ |C_{s}| − (m − 1) ≥ |C_{s}| − q^{−1}|C_{s}| ≥ |C_{s}|(1 − q^{−1}). As q^{−1} ≤ 10^{−2} and q^{−1}|C_{s}| ≥ m ≥ ηn, by Lemma 34 we have, for all 1 ≤ s < t ≤ k,

|d_{H,G}(C_{s}^{∗}, C_{t}^{∗}) − d_{H,G}(C_{s}, C_{t})| ≤ 5q^{−1}  (69)

and

|d_{H,G}(C_{s}^{∗}, C_{t}^{∗})^{2} − d_{H,G}(C_{s}, C_{t})^{2}| ≤ 9q^{−1}.  (70)

5.2. Defect form of the Cauchy–Schwarz inequality. As in [60], the following ‘defect’ form of the Cauchy–Schwarz inequality will be used in the proof of Theorem 13. Lemma 36. Let y_{1}, …, y_{v} ≥ 0 be given. Suppose 0 ≤ ϱ = u/v < 1, and ∑_{1≤i≤u} y_{i} = αϱ ∑_{1≤i≤v} y_{i}. Then

∑_{1≤i≤v} y_{i}^{2} ≥ \frac{1}{v} (1 + (α − 1)^{2} \frac{ϱ}{1 − ϱ}) \{ ∑_{1≤i≤v} y_{i}\}^{2}.  (71)

Since it is for the same price, we prove a weighted version of Lemma 36. The statement and proof of Lemma 37 below are from [24] (see also [25, 60]). Lemma 37. Let σ_{i} and d_{i} (i ∈ I) be non-negative reals with ∑_{i∈I} σ_{i} = 1. Set d = ∑_{i∈I} σ_{i}d_{i}. Let J ⊂ I be a proper subset of I such that ∑_{j∈J} σ_{j} = σ < 1 and

∑_{j∈J} σ_{j}d_{j} = σ(d + μ).

Then

∑_{i∈I} σ_{i}d_{i}^{2} ≥ d^{2} + \frac{μ^{2}σ}{1 − σ} .  (72)

Proof. Let u_{J} = (\sqrt{σ_{j}})_{j∈J}, v_{J} = (\sqrt{σ_{j}}d_{j})_{j∈J}, u_{I\J} = (\sqrt{σ_{i}})_{i∈I\J}, and v_{I\J} = (\sqrt{σ_{i}}d_{i})_{i∈I\J}.

We use the Cauchy–Schwarz inequality in the form | ⟨x, y⟩ |^{2} ≤ ∥x∥^{2}∥y∥^{2}. Taking x = u_{J} and y = v_{J} and x = u_{I\J} and y = v_{I\J}, respectively, we infer that

( ∑_{j∈J} σ_{j}d_{j})^{2} ≤ ∑_{j∈J} σ_{j} ∑_{j∈J} σ_{j}d_{j}^{2},

and

( ∑_{i∈I\J} σ_{i}d_{i})^{2} ≤ ∑_{i∈I\J} σ_{i} ∑_{i∈I\J} σ_{i}d_{i}^{2}.

Therefore

∑_{i∈I} σ_{i}d_{i}^{2} ≥ \frac{1}{σ} ( ∑_{j∈J} σ_{j}d_{j})^{2} + \frac{1}{1 − σ} ( ∑_{i∈I−J} σ_{i}d_{i})^{2}

= σ(d + μ)^{2} + (1 − σ) (d − \frac{σμ}{1 − σ} )^{2} = d^{2} + \frac{μ^{2}σ}{1 − σ} ,

as required. □

Proof of Lemma 36. To prove Lemma 36, simply take σ_{i} = 1/v and d_{i} = y_{i} (1 ≤ i ≤ v) in Lemma 37. Then d = v^{−1} ∑_{1≤i≤v} y_{i}, σ = ϱ, and μ = (α−1)d. Inequality (72) then reduces to (71). □

5.3. The index of a partition. Similarly to [60], we define the index ind(R) of an equitable partition R = (C_{i})_{0}^{r} of V = V (G) to be

ind(R) = \frac{2}{r^{2}} ∑_{1≤i<j≤ℓ} d_{H,G}(C_{i}, C_{j})^{2}.

Note that trivially 0 ≤ ind(R) < 1.

5.4. The index of subpartitions. Our aim now is to show that, for Q = Q(P) defined as above, we have ind(Q) ≥ ind(P) + ε^{5}/100.

5.4.1. The draw case. We start with the following lemma. Lemma 38. Suppose 1 ≤ s < t ≤ k. Then

\frac{1}{q^{2}} ∑_{i, j=1}^{q} d_{H,G}(C_{s}(i), C_{t}(j))^{2} ≥ d_{H,G}(C_{s}, C_{t})^{2} − \frac{ε^{5}}{100}.

Proof. By the (P_{0}, η)-uniformity of G and the fact that (C_{s}, C_{t}) ≺ P_{0}, we have

\frac{1}{q^{2}} ∑_{1≤i≤q} ∑_{1≤j≤q}d_{H,G}(C_{s}(i), C_{t}(j)) = \frac{1}{q^{2}} ∑_{i, j} \frac{e_{H}(C_{s}(i), C_{t}(j))}{e_{G}(C_{s}(i), C_{t}(j))}

≥ ∑_{i, j} \frac{e_{H}(C_{s}(i), C_{t}(j))}{(1 + η)q^{2}p|C_{s}(i)||C_{t}(j)|} = \frac{e_{H}(C_{s}^{∗}, C_{t}^{∗})}{(1 + η)p|C_{s}^{∗}||C_{t}^{∗}|}

≥ \frac{1 − η}{1 + η} d_{H,G}(C_{s}^{∗}, C_{t}^{∗}) ≥ d_{H,G}(C_{s}^{∗}, C_{t}^{∗}) − 2η.

Thus, by the Cauchy–Schwarz inequality, we have

\frac{1}{q^{2}} ∑_{1≤i≤q} ∑_{1≤j≤q} d_{H,G}(C_{s}(i), C_{t}(j))^{2} ≥ d_{H,G}(C_{s}^{∗}, C_{t}^{∗})^{2} − 4η.

Furthermore, by (70), we have d_{H,G}(C_{s}^{∗}, C_{t}^{∗})^{2} ≥ d_{H,G}(C_{s}, C_{t})^{2} − 9q^{−1}. Since we have 9q^{−1} + 4η ≤ ε^{5}/100, the lemma follows. □

5.4.2. The winning case. The inequality in Lemma 38 may be improved if (C_{s}, C_{t}) is an (ε, H, G)-irregular pair, as shows the following result. Lemma 39. Let 1 ≤ s < t ≤ k be such that (C_{s}, C_{t}) is not (ε, H, G)-regular. Then

\frac{1}{q^{2}} ∑_{i, j=1}^{q} d_{H,G}(C_{s}(i), C_{t}(j))^{2} ≥ d_{H,G}(C_{s}, C_{t})^{2} + \frac{ε^{4}}{40} − \frac{ε^{5}}{100}.

Proof. Let X = X(s, t) ⊂ C_{s}, Y = Y (s, t) ⊂ C_{t} be as in the definition of Q. Let X^{∗} ⊂ X be the maximal subset of X that is the union of blocks of Q, and similarly for Y^{∗} ⊂ Y. Without loss of generality, we may assume that X^{∗} = ⋃_{1≤i≤q_{s}} C_{s}(i), and Y^{∗} = ⋃_{1≤j≤q_{t}} C_{t}(j). Note that |X^{∗}| ≥ |X| − 2^{k−1}(m − 1) ≥ |X|(1 − 2^{k−1}m/|X|) ≥ |X|(1 − 2^{k−1}/qε) = |X|(1 − 1/ε2^{k+1}), and similarly |Y^{∗}| ≥ |Y |(1 − 1/ε2^{k+1}). However, we have 1/ε2^{k+1} ≤ 10^{−2} and |X|/ε2^{k+1}, |Y |/ε2^{k+1} ≥ ηn. Thus, by Lemma 34, we have |d_{H,G}(X^{∗}, Y^{∗}) − d_{H,G}(X, Y)| ≤ 5/ε2^{k+1}. Moreover, by (69), we have |d_{H,G}(C_{s}^{∗}, C_{t}^{∗}) − d_{H,G}(C_{s}, C_{t})| ≤ 5q^{−1}. Since |d_{H,G}(X, Y) − d_{H,G}(C_{s}, C_{t})| ≥ ε and 5q^{−1} + 5/ε2^{k+1} ≤ ε/2, we have

|d_{H,G}(X^{∗}, Y^{∗}) − d_{H,G}(C_{s}^{∗}, C_{t}^{∗})| ≥ ε/2.  (73)

For later reference, let us note that q_{s}m = |X^{∗}| ≥ |X| − 2^{k−1}m ≥ ε|C_{s}| − 2^{k−1}m ≥ εqm − 2^{k−1}m, and hence q_{s} ≥ εq − 2^{k−1} ≥ εq/2. Similarly, we have q_{t} ≥ εq/2. Let us now set y_{ij} = d_{H,G}(C_{s}(i), C_{t}(j)) for i, j = 1, …, q. In the proof of Lemma 38 we checked that

∑_{1≤i≤q} ∑_{1≤j≤q} y_{ij} ≥ \frac{1 − η}{1 + η} q^{2}d_{H,G}(C_{s}^{∗}, C_{t}^{∗}) ≥ (1 − 2η)q^{2}d_{H,G}(C_{s}^{∗}, C_{t}^{∗}).

Similarly, one has

∑_{1≤i≤q} ∑_{1≤j≤q} y_{ij} ≤ (1 + 3η)q^{2}d_{H,G}(C_{s}^{∗}, C_{t}^{∗}),

∑_{1≤i≤q_{s}} ∑_{1≤j≤q_{t}} y_{ij} ≥ (1 − 2η)q_{s}q_{t}d_{H,G}(X^{∗}, Y^{∗}),

and

∑_{1≤i≤q_{s}} ∑_{1≤j≤q_{t}} y_{ij} ≤ (1 + 3η)q_{s}q_{t}d_{H,G}(X^{∗}, Y^{∗}).

Let us set ϱ = q_{s}q_{t}/q^{2} ≥ ε^{2}/4, and d_{s,t}^{∗} = d_{H,G}(C_{s}^{∗}, C_{t}^{∗}). We now note that by (73) we either have

\begin{matrix}∑_{1≤i≤q_{s}} ∑_{1≤j≤q_{t}} y_{ij} ≥ \frac{1 − 2η}{1 + 3η} · \frac{q_{s}q_{t}}{q^{2}} (1 + \frac{ε}{2(d_{s,t}^{∗})^{2}} ) ∑_{1≤i≤q} ∑_{1≤j≤q} y_{ij} \\ ≥ ϱ (1 + \frac{ε}{3(d_{s,t}^{∗})^{2}} ) ∑_{1≤i≤q} ∑_{1≤j≤q} y_{ij} & , \end{matrix}

or else

\begin{matrix}∑_{1≤i≤q_{s}} ∑_{1≤j≤q_{t}} y_{ij} ≤ \frac{1 + 3η}{1 − 2η} · \frac{q_{s}q_{t}}{q^{2}} (1 − \frac{ε}{2(d_{s,t}^{∗})^{2}} ) ∑_{1≤i≤q} ∑_{1≤j≤q} y_{ij} \\ ≤ ϱ (1 − \frac{ε}{3(d_{s,t}^{∗})^{2}} ) ∑_{1≤i≤q} ∑_{1≤j≤q} y_{ij} & . \end{matrix}

We may now apply Lemma 36 to conclude that

∑_{1≤i≤q} ∑_{1≤j≤q} y_{ij}^{2} ≥ \frac{1}{q^{2}} (1 + \frac{ε^{2}}{9(d_{s,t}^{∗})^{2}} · \frac{ϱ}{1 − ϱ}) \{ ∑_{1≤i≤q} ∑_{1≤j≤q} y_{ij}\}^{2}

≥ \frac{1}{q^{2}} (1 + \frac{ε^{2}ϱ}{9(d_{s,t}^{∗})^{2}} ) \{q^{2}(1 − 2η)d_{s,t}^{∗}\}^{2}

≥ q^{2}(1 − 4η) ((d_{s,t}^{∗})^{2} + \frac{ε^{2}ϱ}{9}) ≥ q^{2} ((d_{s,t}^{∗})^{2} + \frac{ε^{2}ϱ}{10} − 4η) .

Therefore

\begin{aligned}\frac{1}{q^{2}} ∑_{1≤i≤q} & ∑_{1≤j≤q} d_{H,G}(C_{s}(i), C_{t}(j))^{2} ≥ d_{H,G}(C_{s}^{∗}, C_{t}^{∗})^{2} + \frac{ε^{2}ϱ}{10} − 4η \\ & ≥ d_{H,G}(C_{s}, C_{t})^{2} + \frac{ε^{4}}{40} − (9η^{−1} + 4η) ≥ d_{H,G}(C_{s}, C_{t})^{2} + \frac{ε^{4}}{40} − \frac{ε^{5}}{100}, \end{aligned}

as required. □

5.5. Proof of Theorem 13. We are now ready to prove the main lemma needed in the proof of Theorem 13. Lemma 40. Suppose k ≥ 1 and 0 < ε ≤ 1/2 are such that 4^{k} ≥ 1800ε^{−5}. Let G = G^{n} be a (P_{0}, η)-uniform graph of order n ≥ n_{0} = n_{0}(k) = k4^{2k+1}, where P_{0} = (V_{i})_{1}^{ℓ} is a partition of V = V (G), and assume that η ≤ η_{0} = η_{0}(k) = 1/k4^{k+1}. Let H ⊂ G be a spanning subgraph of G. If P = (C_{i})_{0}^{k} is an (ε, H, G)-irregular (ε, k)-equitable partition of V = V (G) refining P_{0}, then there is a k′-equitable partition Q = (C′_{i})_{0}^{k′} of V such that (i) Q refines P, (ii) k′ = k4^{k}, (iii) |C′_{0}| ≤ |C_{0}| + n4^{−k}, and (iv) ind(Q) ≥ ind(P) + ε^{5}/100.

Proof. Let P be as in the lemma. We show that the k′-equitable partition Q = (C′_{i})_{0}^{k′} defined from P as above satisfies (i)–(iv). In view of Lemma 35, it only remains to check (iv). By Lemmas 38 and 39, we have

ind(Q) = \frac{2}{(kq)^{2}} ∑_{1≤i≤q} ∑_{1≤j≤q} d_{H,G}(C′_{i}, C′_{j})^{2}

≥ \frac{2}{k^{2}} ∑_{1≤s<t≤k} \frac{1}{q^{2}} ∑_{1≤i≤q} ∑_{1≤j≤q} d_{H,G}(C_{s}(i), C_{t}(j))^{2}

≥ \frac{2}{k^{2}} \{ ∑_{1≤s<t≤k} (d_{H,G}(C_{s}, C_{t})^{2} − \frac{ε^{5}}{100}) + ε\binom{k}{2}\frac{ε^{4}}{40}\}

≥ ind(P) − \frac{ε^{5}}{100} + \frac{ε^{5}}{50} ≥ ind(P) + \frac{ε^{5}}{100}.

This completes the proof of the lemma. □

Proof of Theorem 13. Let ε > 0, k_{0} ≥ 1, and ℓ ≥ 1 be given. We may assume that ε ≤ 1/2. Pick s ≥ 1 such that 4^{s/4ℓ} ≥ 1800ε^{−5}, s ≥ max{2k_{0}, 3ℓ/ε}, and ε4^{s−1} ≥ 1. Let f(0) = s, and put inductively f(t) = f(t − 1)4^{f(t−1)} (t ≥ 1). Let t_{0} = ⌊100ε^{−5}⌋ and set N = max{n_{0}(f(t)) : 0 ≤ t ≤ t_{0}} = f(t_{0})4^{2f(t_{0})+1}, K_{0} = max{6ℓ/ε, N}, and η = η(ε, k_{0}, ℓ) = min{η_{0}(f(t)) : 0 ≤ t ≤ t_{0}} = 1/4f(t_{0} + 1) > 0. Finally, we take N_{0} = N_{0}(ε, k_{0}, ℓ) = K_{0}. We claim that η, K_{0}, and N_{0} as defined above will do.

To prove our claim, let G = G^{n} be a fixed (P_{0}, η)-uniform graph with n ≥ N_{0}, where P_{0} = (V_{i})_{1}^{ℓ} is a partition of V = V (G). Furthermore, let H ⊂ G be a spanning subgraph of G. We have n ≥ N_{0} = K_{0}. Suppose t ≥ 0. Let us say that an equitable partition P^{(t)} = (C_{i})_{0}^{k} of V is t-valid if (i) P^{(t)} refines P_{0}, (ii) s/4ℓ ≤ k ≤ f(t), (iii) ind{P^{(t)}} ≥ tε^{5}/100, and (iv) |C_{0}| ≤ εn(1 − 2^{−(t+1)}). We now verify that a 0-valid partition P^{(0)} of V does exist. Let m = ⌈n/s⌉, and let Q be a partition of V with all blocks of cardinality m, except for possibly one, which has cardinality at most m − 1, and moreover such that each V_{i} (1 ≤ i ≤ ℓ) contains ⌊|V_{i}|/m⌋ blocks of Q. Grouping at most ℓ blocks of Q into a single block C_{0}, we arrive at an equitable partition P^{(0)} = (C_{i})_{0}^{k} of V that is 0-valid. Indeed, (i) is clear, and to check (ii) note that k ≤ n/m ≤ s = f(0), and that there is 1 ≤ i ≤ ℓ such that |V_{i}| ≥ n/ℓ, and so k ≥ ⌊|V_{i}|/m⌋ ≥ ⌊(n/ℓ)/⌈n/s⌉⌋ ≥ (1/2){(n/ℓ)/(2n/s)} = s/4ℓ. Also, (iii) is trivial and (iv) does follow, since |C_{0}| < ℓm ≤ ℓ⌈nε/3ℓ⌉ ≤ nε/2 as n ≥ K_{0} ≥ 6ℓ/ε.

Now note that if there is a t-valid partition P^{(t)} of V, then t ≤ t_{0} = ⌊100ε^{−5}⌋, since ind{P^{(t)}} ≤ 1. Suppose t is the maximal integer for which there is a t-valid partition P^{(t)} of V. We claim that P^{(t)} is (ε, H, G)-regular. Suppose to the contrary that P^{(t)} is not (ε, H, G)-regular. Then simply note that Lemma 40 gives a (t + 1)- valid equitable partition P^{(t+1)} = Q = Q(P^{(t)}), contradicting the maximality of t. This completes the proof of Theorem 13. □

6. Local conditions for regularity

As briefly discussed in the introduction, our aim in this section is to discuss a well-known ‘local’ condition for regularity. It should be stressed that in Sections 6 and 7, we are concerned with dense graphs, that is, we are in the context of the original regularity lemma. (See Section 6.5 for a very brief discussion on extensions of the results in Section 6 to the sparse case.)

6.1. The basic argument. In this section, we give a result of Lindsey (see the proof of the upper bound in Theorem 15.2 in [22]) because it contains one of the key ideas used in developing local conditions for regularity.

Let H = (h_{ij}) be an n by n Hadamard matrix. Thus H is a {±1}-matrix whose rows are pairwise orthogonal. Let

disc(H; a, b) = max_{I,J} | ∑_{i∈I, j∈J} h_{ij}|,  (74)

where the maximum is taken over all sets of rows I and all sets of columns J with |I| = a and |J| = b. We also let the discrepancy of H be

disc(H) = max_{a,b} disc(H; a, b),  (75)

where the maximum is taken over all 1 ≤ a ≤ n and 1 ≤ b ≤ n.

Theorem 41. For any n by n Hadamard matrix H, and any 1 ≤ a ≤ n and 1 ≤ b ≤ n, we have

disc(H; a, b) ≤ \sqrt{abn}.  (76)

Proof. Let the rows of H be v_{1}, …, v_{n}, and fix a and b. Suppose, without loss of generality, that I = {1, …, a} and J = {1, …, b}. Let also 1_{J} = (1, …, 1, 0, …)^{T} ∈ ℝ^{n} be the characteristic vector of J. By the Cauchy–Schwarz inequality, we have

| ∑_{I,J} h_{ij}| = |⟨ ∑_{i∈I} v_{i}, 1_{J}⟩| ≤ ∥ ∑_{i∈I} v_{i}∥\sqrt{|J|} = ∥ ∑_{i∈I} v_{i}∥\sqrt{b}.  (77)

From the pairwise orthogonality of the vectors v_{i}, we have

∥ ∑_{i∈I} v_{i}∥ = \sqrt{∑_{i∈I} ∥v_{i}∥^{2}} = \sqrt{n|I|} = \sqrt{na}.  (78)

Plugging (78) into (77), we have

| ∑_{I,J} h_{ij}| ≤ \sqrt{abn},

and the result follows. □

Corollary 42. The discrepancy disc(H) of an n by n Hadamard matrix H satisfies disc(H) ≤ n^{3/2}.

An easy generalization of Theorem 41 above concerns the case in which we weaken the condition that the rows of H should be precisely orthogonal. Let us say that two vectors u, v ∈ ℝ^{n} are ε-quasi-orthogonal if | ⟨u, v⟩ | ≤ εn. Our next result roughly states that if the rows of an n by n matrix H are o(1)-quasi-orthogonal, then the discrepancy of H is o(n^{2}). Theorem 43. Let δ > 0 be fixed and let H be an n by n matrix whose rows v_{i} (1 ≤ i ≤ n) are δ-quasi-orthogonal and ∥v_{i}∥ ≤ \sqrt{n} for all 1 ≤ i ≤ n. Then

disc(H; a, b) ≤ n^{2}\sqrt{2δ}  (79)

for all a ≥ 1/δ and all b ≥ 1.

Proof. We proceed exactly in the same manner as in the proof of Theorem 41. However, instead of (78), we observe that

∥ ∑_{i∈I} v_{i}∥^{2} = ⟨ ∑_{i∈I} v_{i}, ∑_{i∈I} v_{i}⟩ = ∑_{i∈I} ⟨v_{i}, v_{i}⟩ + ∑_{i≠j} ⟨v_{i}, v_{j}⟩ ,  (80)

where the last sum is over all i ≠ j with i, j ∈ I. The result now follows from the hypotheses on the ∥v_{i}∥ and on the ⟨v_{i}, v_{j}⟩. Indeed, the right-hand side of (80) is at most

an + 2\binom{a}{2}δn ≤ a^{2}δn (1 + \frac{1}{aδ} ) ≤ 2a^{2}δn.  (81)

Therefore, the right-hand side of (77) is at most \sqrt{2a^{2}bδn} ≤ n^{2}\sqrt{2δ}. Theorem 43 follows. □

Before we proceed, let us observe that, in fact, the hypothesis of δ-quasi-ortho-gonality of the v_{i} (1 ≤ i ≤ n) in Theorem 43 may be further weakened to

⟨v_{i}, v_{j}⟩ ≤ δn for all i ≠ j with 1 ≤ i, j ≤ n.  (82)

Indeed, hypothesis (82) above suffices for us to estimate the last sum in (80). The reader may also observe that, in fact, it suffices to require that the inequality in (82) should hold for most pairs {i, j} with i ≠ j, with little loss in the conclusion (79). We omit the details.

Finally, let us observe that Theorem 41 concerns matrices in which the number of +1s is about the same as the number of −1s, and hence the average entry is about 0. In general, we shall be interested in the case in which the rows of our matrix are pairwise quasi-orthogonal (or, more generally, the rows satisfy (82)), the average entry is about 0, but the entries are not necessarily ±1. Adapting carefully the argument in the proof of Theorem 41 to this more general case gives Lemma 45, to be discussed in the Section 6.3.

6.2. The converse. In the previous section, we proved that the pairwise orthogonality of the rows of a {±1}-matrix has as a somewhat unexpected consequence the fact that the matrix must have small discrepancy. In this section, we prove that o(n^{2}) discrepancy for an n by n matrix implies the existence of only o(n^{2}) pairs of rows that are ‘substantially’ non-orthogonal (in fact, we prove that the number of pairs {i, j} violating the condition in (82) is o(n^{2})). Thus, roughly speaking, we shall prove the converse of the results in Section 6.1. Theorem 44. Let δ > 0 be a real number and let H = (h_{ij}) be an n by n matrix with entries in {±1}. Let the rows of H be v_{i} (1 ≤ i ≤ n). Let D be the graph on V = V (D) = [n] = {1, …, n} whose edges are the pairs {i, j} (i ≠ j) for which we have

⟨v_{i}, v_{j}⟩ > δn.  (83)

If D is such that e(D) = |E(D)| ≥ δn^{2}, then

disc(H) > \frac{1}{2}δ^{2}n^{2}.  (84)

Before we give the proof of Theorem 44, let us give the underlying argument in its simplest form. Let us suppose that we have the following convenient set-up:

v_{1} = 1 = (1, …, 1) ∈ ℝ^{n}  (85)

and

⟨v_{1}, v_{i}⟩ = Ω(n).  (86)

for all i ∈ I, where |I| = Ω(n). Clearly, we may restate (86) by saying that all the vectors v_{i} (i ∈ I) have a ‘surplus’ of +1s of order Ω(n). Since we have |I| = Ω(n) such vectors v_{i}, if we sum all the entries of these v_{i} we obtain a discrepancy of Ω(n^{2}).

To prove Theorem 44, we concentrate our attention on a vertex of high degree in D, and we consider a subset of the columns of H so that the simplifying hypothesis (85) holds.

Proof of Theorem 44. We start by noticing that the average degree of D is ≥ 2δn. Let i_{0} ∈ [n] = V (D) be a vertex of D with degree ≥ 2δn. We let I be the neighbourhood Γ(i_{0}) of i_{0} in D. Therefore,

|I| ≥ 2δn.  (87)

For α ∈ {+, −}, let

J_{α} = {j ∈ [n]: h_{i_{0}j} = α}.  (88)

Clearly, we have v_{i_{0}} = 1_{J_{+}} −1_{J_{−}}, where we write 1_{S} for the characteristic vector of a set S. For any i ∈ [n] and α ∈ {+, −}, let v_{i}^{α} be the restriction of v_{i} = (h_{ij})_{1≤j≤n} to J_{α}, that is,

v_{i}^{α} = (h_{ij})_{j∈J_{α}}.  (89)

For any i ∈ I = Γ(i_{0}), we have

⟨v_{i_{0}}^{+}, v_{i}^{+}⟩ + ⟨v_{i_{0}}^{−}, v_{i}^{−}⟩ = ⟨v_{i_{0}}, v_{i}⟩ > δn.

Therefore, either

⟨1_{J_{+}}, v_{i}^{+}⟩ = ⟨v_{i_{0}}^{+}, v_{i}^{+}⟩ > \frac{1}{2}δn,  (90)

or else

⟨−1_{J_{−}}, v_{i}^{−}⟩ = ⟨v_{i_{0}}^{−}, v_{i}^{−}⟩ > \frac{1}{2}δn.  (91)

Let

I_{+} = {i ∈ I = Γ(i_{0}): (90) holds},

and let

I_{−} = {i ∈ I = Γ(i_{0}): (91) holds}.

Clearly, I = Γ(i_{0}) = I_{+} ∪ I_{−} and hence

max\{|I_{+}|, |I_{−}|\} ≥ \frac{1}{2}|I| ≥ δn,  (92)

where we used (87). Let us now put S_{α} = ∑ h_{ij} for α ∈ {+, −}, where the sum runs over all i ∈ I_{α} and j ∈ J_{α}. Observe that then

S_{+} = ∑ \{h_{ij}: i ∈ I_{+}, j ∈ J_{+}\} = ⟨ ∑_{i∈I_{+}} v_{i}^{+}, 1_{J_{+}}⟩ > \frac{1}{2}δn|I_{+}|,

and

S_{−} = ∑ \{h_{ij}: i ∈ I_{−}, j ∈ J_{−}\} = ⟨ ∑_{i∈I_{−}} v_{i}^{−}, 1_{J_{−}}⟩ < −\frac{1}{2}δn|I_{−}|,

where the inequalities follow from (90) and (91). We now observe that (92) gives that

disc(H) ≥ max\{|S_{+}|, |S_{−}|\} > max\{|I_{+}|, |I_{−}|\}\frac{1}{2}δn ≥ \frac{1}{2}δ^{2}n^{2},  (93)

which completes the proof. □

We shall discuss the ‘full’ version of Theorem 44 above in Section 6.3.2.

6.3. The general results. We now state the ‘general versions’ of the results in Sections 6.1 and 6.2. We follow [19]. The results in this section are stated for graphs instead of matrices.

6.3.1. The sufficiency of the condition. Recall that we write Γ(x) = Γ_{G}(x) for the neighbourhood of a vertex x in a graph G. Moreover, if B ⊂ V (G) is a subset of vertices of our graph G, we write d_{B}(x) for the degree |Γ(x) ∩ B| of x into B, and, similarly, we write d_{B}(x, x′) for the ‘joint degree’ |Γ(x) ∩ Γ(x′) ∩ B| of x and x′ into B.

We now state the ‘full’ version of Theorem 43 (see also the comment concerning the weaker hypothesis (82)). Theorem 45. Let ε be a constant with 0 < ε < 1. Let G = (V, E) be a graph with (A, B) a pair of disjoint, nonempty subsets of V with |A| ≥ 2/ε. Set ϱ = d(A, B) = e(A, B)/|A||B|. Let D be the collection of all pairs {x, x′} of vertices of A for which

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

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

We only give a brief sketch for the proof of Theorem 45 here. The first step is to construct an A by B ‘adjacency’ matrix M, whose entries are −1 and λ = (1−ϱ)/ϱ. A −1 entry indicates the absence of the edge and the entry λ indicates the presence of the edge. It is not difficult to check that the discrepancy of this matrix M is tightly connected with the regularity of the pair (A, B). Indeed, we have

disc(M; a′, b′) = \frac{1}{ϱ} max_{A′, B′} |e(A′, B′) − ϱ|A′||B′||,  (94)

where the maximum is taken over all A′ ⊂ A and B′ ⊂ B with |A′| = a′ and |B′| = b′. On the other hand, by making use of the hypothesis on D, a careful application of Lindsey’s argument gives that

disc(M; a′, b′) ≤ \frac{1}{ϱ}(16ε)^{1/5}a′b′  (95)

for all a′ ≥ ε|A| and b′ ≥ ε|B|. Theorem 45 follows from (94) and (95). See [19] for the details.

6.3.2. The necessity of the condition. We now turn to the converse of Theorem 45. The ‘full’ version of Theorem 44 is as follows. Theorem 46. Let G = (V, E) be a graph with (A, B) an ε-regular pair of disjoint, nonempty subsets of V, having density d(A, B) = e(A, B)/|A||B| = ϱ, where ϱ|B| ≥ 1 and 0 < ε < 1. Then

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

(ϱ − ε)|B| < d_{B}(x), d_{B}(x′) < (ϱ + ε)|B|,

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

d_{B}(x, x′) < (ϱ + ε)^{2}|B|.

Theorem 46 may be proved by adapting the proof of Theorem 44. See [19] for the details.

6.4. Algorithmic versions. Let us briefly discuss some algorithmic aspects. The reader is referred to [37] for a survey.

In algorithmic applications of regularity, once an ε-regular partition is obtained, one typically makes use of constructive versions of results such as the embedding lemma, Lemma 25. The reader will have no difficulty in observing that an efficient algorithm is implied in the proof of Lemma 25.

The question is, then, whether ε-regular partitions may be constructed efficiently. It turns out that this is indeed the case [4, 5]. The main tool to prove this is the local characterization of regularity that we have been discussing in this section. In fact, Theorems 45 and 46 imply Lemma 47 below (see [4, 5, 19]), which is the key ingredient of the constructive version of the regularity lemma given in [4, 5].

Recall that a bipartite graph B = (U, W; E) with vertex classes U and W and edge set E is said to be ε-regular if (U, W) is an ε-regular pair with respect to B. Thus, a witness to the ε-irregularity of B is a pair (U′, W′) with U′ ⊂ U, W′ ⊂ W, |U′|, |W′| ≥ εn, and |d_{B}(U′, W′) − d_{B}(U, W)| > ε. Below, we write M(n) for the time required to square an n × n matrix with entries in {0, 1} over the integers. By a result of Coppersmith and Winograd [17], we have M(n) = O(n^{2.376}). (We leave it as an easy exercise for the reader to see how matrix multiplication comes into play here; without fast matrix multiplication, we would have an algorithm with running time O(n^{3}) in Lemma 47 below.)

Lemma 47. There exists an algorithm A for which the following holds. When A receives as input an ε > 0 and a bipartite graph B = (U, W; E) with |U| = |W | = n ≥ (2/ε)^{5}, it either correctly asserts that B is ε-regular, or else it returns a witness for the ε′-irregularity of B, where ε′ = ε′_{A}(ε) = ε^{5}/16. The running time of A is O(M(n)).

Note that Lemma 47 leaves open what the behaviour of A should be when B is ε-regular but is not ε′-regular. Despite this fact, Lemma 47 does indeed imply the existence of a polynomial-time algorithm for finding ε-regular partitions of graphs. A moment’s thought should make it clear that what is required is an algorithmic version of Lemma 40. Lemma 47 readily provides such a result. We leave the proof of this assertion as an exercise for the reader.

Summing up the results discussed so far, we have the following theorem, which is an algorithmic version of Szemerédi’s regularity lemma [4, 5].

Theorem 48. There is a deterministic algorithm B and functions K_{0}(ε, k_{0}) and N_{0}(ε, k_{0}) for which the following holds. On input G = G^{n}, 0 < ε ≤ 1, and k_{0} ≥ 1, where n ≥ N_{0}(ε, k_{0}), algorithm B returns an ε-regular, (ε, k)-equitable partition for G in time O(M(n)), where k_{0} ≤ k ≤ K_{0}(ε, k_{0}).

Let us observe that the constant implied in the big O notation in Theorem 48 depends on ε and k_{0}.

In [41], we shall show how to improve on the running time given in Lemma 47 (at the cost of decreasing the value of ε′ = ε′(ε) substantially). The key idea is to make use of the quasi-random property to be discussed in Section 7. The algorithm for constructing ε-regular partitions given in [41] has running time O(n^{2}) for graphs of order n, where, again, the implicit constant depends on ε and k_{0}.

The algorithms we have discussed so far are all deterministic. If one allows randomization, one may develop algorithms that run in O(n) time, as shown by Frieze and Kannan [27, 28].

6.4.1. A coNP-completeness result. The reader may find it unsatisfactory that, strictly speaking, we did not solve the problem of characterizing precisely the εregular pairs. Indeed, Lemma 47 can only tell the difference between ε′_{A}(ε)-regular pairs and ε-irregular pairs, and ε′_{A}(ε) ≪ ε. This is, by no means, an accident. Consider the decision problem below.

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

It should be clear that, in the case in which the answer to Problem 49 is negative for a given instance, we would like to have a witness for the ε-irregularity of the given pair. Indeed, an algorithm that is able to solve Problem 49 and is also able to provide such a witness in the case in which the answer is negative would prove Lemma 47 with ε′ = ε. Unfortunately, such an algorithm does not exist, unless P = NP, as shows the following result of Alon, Duke, Lefmann, Rödl, and Yuster [4, 5].

Theorem 50. Problem 49 is coNP-complete.

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

6.5. The sparse case. As proved in [38], Theorems 45 and 46 do not generalize to graphs of vanishing density. However, in view of the applicability of those results, it seems worth pursuing the sparse case. In [38], we prove that natural generalizations of Theorems 45 and 46 do hold for subgraphs of sparse random graphs. Examples of applications of these generalizations appear in [3] (cf. Theorem 1.5) and [40]. We do not go into the details here.

7. A new quasi-random property

In this section, we present a new quasi-random graph property, in the sense of Chung, Graham, and Wilson [15]. In the introduction and in Section 3.2.3, we very briefly discussed the basics of quasi-randomness, and mentioned the close relationship between quasi-randomness, ε-regularity, and the regularity lemma as a strong motivation for studying quasi-random graph properties.

In Section 6, we discussed ‘local’ conditions for regularity, and observed that these conditions were the key for developing a O(n^{2.376})-time algorithm that checks whether a given bipartite graph is regular (see Lemma 47). In turn, this led to a O(n^{2.376})-time algorithm for finding regular partitions of graphs. The quasi-random property that we present in this section allows one to check regularity, somewhat surprisingly, in time O(n^{2}). Since we deal with dense input graphs, this running time is proportional to the input size, and hence we have a linear time algorithm. (The corresponding linear time algorithm for finding regular partitions of graphs, which is based on some additional ideas, will be presented in [41].)

The proof of the fact that our property is indeed a quasi-random property will make use of the sparse regularity lemma, Theorem 15. To simplify the notation, we restrict our discussion to the case of graphs with density ∼ 1/2. Moreover, we deal with quasi-randomness and arbitrary graphs, instead of regularity and bipartite graphs. We hope that the reader finds the correspondence between these two contexts clear.

7.1. Basic definitions. We start with the definition of a standard quasi-random graph property.

Definition 51 ((1/2, ε, δ)-quasi-randomness). 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 |.  (96)

Before we proceed, we need to introduce a technical definition concerning graphs with uniformly distributed edges.

Definition 52 ((ϱ, A)-uniformity). If 0 < ϱ ≤ 1 and A are reals, we say that an n-vertex graph J = J^{n} is (ϱ, A)-uniform if, for all U, W ⊂ V (J) with U ∩ W = ∅, we have

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

where r = ϱn.

As it will become clear later, we shall be mainly concerned with (ϱ, A)-uniform graphs J with constant average degree, that is, graphs J = J^{n} with O(n) edges. The construction of such (ϱ, A)-uniform graphs J = J^{n} with linearly many edges will be briefly discussed in Section 7.3.

In the sequel, when dealing with a (ϱ, A)-uniform graph J = J^{n}, we usually write r for ϱn. Let us remark for later reference that the following fact, whose simple proof will be given in Section 7.3, holds. Fact 53. If J is a (ϱ, A)-uniform graph, then, for any U ⊂ V (J), we have

|e_{J}(U) − ϱ\binom{|U|}{2}| ≤ A\sqrt{r}|U|.  (98)

We shall now define a property for n-vertex graphs G = G^{n}, based on a fixed (ϱ, A)-uniform graph J = J^{n} with the same vertex set as G. Below, we write ij ∈ J to mean that ij is an edge of the graph J. We recall that we denote the neighbourhood of a vertex x in a graph G by Γ(x) = Γ_{G}(x), and we write X △ Y for the symmetric difference of X and Y.

Definition 54 (Property P_{J,△}(ε)). Let G = G^{n} and J = J^{n} be n-vertex graphs on the same vertex set. Let 0 < ε ≤ 1 be a real number. We say that G satisfies property P_{J,△}(ε) if we have

∑_{ij∈J} ||Γ_{G}(i) △ Γ_{G}(j)| − \frac{1}{2}n| ≤ \frac{1}{2}εne(J).  (99)

Our new quasi-random property is P_{J,△}(ε) above. It should be now clear why it is interesting for us to have (ϱ, A)-uniform graphs J with as few edges as possible: the number of terms in the sum in (99) is e(J). Since each term of that sum may be computed in O(n) time if, say, we have access to the adjacency matrix of G, it follows that the time required to verify property P_{J,△}(ε) is O(ne(J)), which is O(n^{2}) if we have linear-sized (ϱ, A)-uniform graphs J.

For technical reasons, we need to introduce a variant of property P_{J,△}(ε).

Definition 55 (Property P′_{J,△}(γ, ε)). Let G = G^{n} and J = J^{n} be n-vertex graphs on the same vertex set. Let 0 < γ ≤ 1 and 0 < ε ≤ 1 be two real numbers. We shall say that G satisfies property P′_{J,△}(γ, ε) if the inequality

||Γ_{G}(i) △ Γ_{G}(j)| − \frac{1}{2}n| ≤ \frac{1}{2}εn  (100)

fails for at most γe(J) edges ij ∈ J of J.

As a quick argument will show, properties P_{J,△}(ε) and P′_{J,△}(γ, ε) are equivalent under suitable assumptions on the parameters; see Lemma 60.

Our main result in Section 7 is that, roughly speaking, properties P_{J,△}(o(1)) and P′_{J,△}(o(1), o(1)) are equivalent to (1/2, o(1), o(1))-quasi-randomness. We make the form of this equivalence precise in the next section.

7.2. The equivalence result. Theorems 56 and 57 below are the main results of Section 7. Intuitively, Theorem 56 states that property P_{J,△}(o(1)) is a sufficient condition for (1/2, o(1), o(1))-quasi-randomness, whereas Theorem 57 states that P′_{J,△}(o(1), o(1)) is a necessary condition. Lemma 60 tells us that P_{J,△}(o(1)) and P′_{J,△}(o(1), o(1)) are equivalent. Theorem 56. For any 0 < ε ≤ 1, 0 < δ ≤ 1, and A ≥ 1, there exist ε_{0} = ε_{0}(ε, δ, A) > 0 and r_{0} = r_{0}(ε, δ, A) ≥ 1 for which the following holds. Suppose G = G^{n} and J = J^{n} are two graphs on the same vertex set. Suppose further that J = J^{n} is a (ϱ, A)-uniform graph with r = ϱn ≥ r_{0}. Then, if G satisfies property P_{J,△}(ε′) for some 0 < ε′ ≤ ε_{0}, then G is (1/2, ε, δ)-quasi-random.

Theorem 57. For any 0 < γ ≤ 1, 0 < ε ≤ 1, and A ≥ 1, there exist ε_{0} = ε_{0}(γ, ε, A) > 0, δ_{0} = δ_{0}(γ, ε, A) > 0, r_{1} = r_{1}(γ, ε, A) ≥ 1, and N_{1} = N_{1}(γ, ε, A) ≥ 1 for which the following holds. Suppose G = G^{n} and J = J^{n} are two graphs on the same vertex set, with n ≥ N_{1}. Suppose further that J = J^{n} is a (ϱ, A)-uniform graph with r = ϱn ≥ r_{1}. Then, if G is (1/2, ε′, δ′)-quasi-random for some 0 < ε′ ≤ ε_{0} and 0 < δ′ ≤ δ_{0}, then property P′_{J,△}(γ, ε) holds for G.

Remark 58. As our previous discussion suggests, it is of special relevance to us that in Theorems 56 and 57 the quantity r = ϱn is not required to grow with n.

Remark 59. We remark that Theorems 56 and 57 basically reduce to the results in Sections 6.1–6.3 if we take J = J^{n} to be the complete graph K^{n}.

Lemma 60. Let a (ϱ, A)-uniform graph J = J^{n} be given, and suppose G = G^{n} is a graph on the same vertex set as J. Then the following assertions hold.

(i) If G satisfies property P′_{J,△}(γ, ε), then G satisfies property P_{J,△}(ε + γ). (ii) If G satisfies property P_{J,△}(ε) and 0 < ε ≤ ε′ ≤ 1, then G satisfies prop-

erty P′_{J,△}(ε/ε′, ε′). We shall prove Theorems 56 and 57 in two separate sections below. Here, we

give the simple proof of Lemma 60.

Proof of Lemma 60. Let J = J^{n} and G = G^{n} be as in the statement of Lemma 60. Suppose first that G has property P′_{J,△}(γ, ε). Then

∑_{ij∈J} ||Γ_{G}(i) △ Γ_{G}(j)| − \frac{1}{2}n| ≤ \frac{1}{2}εne(J) + \frac{1}{2}nγe(J) = \frac{1}{2}(ε + γ)ne(J). (101)

Therefore property P_{J,△}(ε + γ) holds and (i) is proved. To prove (ii), suppose that G satisfies P_{J,△}(ε) and 0 < ε ≤ ε′ ≤ 1. If P′_{J,△}(ε/ε′, ε′) were to fail, then we would have > (ε/ε′)e(J) edges ij of J with

||Γ_{G}(i) △ Γ_{G}(j)| − \frac{1}{2}n| > \frac{1}{2}ε′n.  (102)

But then

∑_{ij∈J} ||Γ_{G}(i) △ Γ_{G}(j)| − \frac{1}{2}n| > \frac{1}{2}ε′n × \frac{ε}{ε′} e(J) = \frac{1}{2}εne(J),  (103)

which contradicts P_{J,△}(ε). Thus P′_{J,△}(ε/ε′, ε′) must hold, and (ii) is proved. □

7.3. The existence of (ϱ, A)-uniform graphs. As promised before, in this section we discuss the construction of suitable (ϱ, A)-uniform graphs J = J^{n} with linearly many edges. We state the following result without proof. Lemma 61. There exist absolute constant r_{0} and n_{0} for which the following holds. Let r ≥ r_{0} be a constant and let n ≥ n_{0} be given. Then we may explicitly construct an adjacency list representation of a particular (ϱ, 5)-uniform graph J = J^{n} on V (J) = [n] with r ≤ ϱn ≤ 2r in time O(n(log n)^{O(1)}).

Lemma 61 may be deduced in a straightforward manner from the celebrated construction of the Ramanujan graphs X^{p,q} of Lubotzky, Phillips, and Sarnak [51] (see also [49, 50, 59]). We mention in passing that, for proving the existence of suitable parameters p and q in the proof of Lemma 61, it suffices to use Dirichlet’s theorem on the density of primes in arithmetic progressions. We omit the details (see [41]).

We also promised to prove Fact 53 in this section.

Proof of Fact 53. We may clearly assume that u = |U| ≥ 2. Note that, for any 1 ≤ s < u, we have 2e(U)\binom{u−2}{s−1} = ∑_{S} e(S, U \ S), where the sum is extended over all S ⊂ U with |S| = s. Thus

e(U) = \frac{1}{2}\binom{u}{s}\binom{u − 2}{s − 1}^{−1} \{ϱ|S||U \ S| + O_{1} (A\sqrt{rs(u − s)})\}  (104)

for any 1 ≤ s < u. We use (104) with s = ⌊u/2⌋. Note that

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

and so

e(U) = ϱ\binom{u}{2} + O_{1} (2A\sqrt{r⌊u/2⌋⌈u/2⌉}) = ϱ\binom{u}{2} + O_{1} (Au\sqrt{r}) ,  (106)

as required. □

In the next two sections, we prove Theorems 56 and 57.

7.4. Proof of Theorem 56. Let constants 0 < ε ≤ 1, 0 < δ ≤ 1, and A ≥ 1 be given. We then put

ε_{0} = ε_{0}(ε, δ, A) = \frac{1}{4}ε^{2}δ^{3} and r_{0} = r_{0}(ε, δ, A) = 2^{6}A^{2}ε^{−4}δ^{−4}.  (107)

For later reference, let us observe that

\frac{A}{2\sqrt{r}_{0}} ≤ \frac{1}{16} < \frac{1}{4},  (108)

and that

\frac{A}{\sqrt{r}_{0}} = \frac{1}{8}ε^{2}δ^{2}.  (109)

Our aim is to show that the values of ε_{0} and r_{0} given in (107) will do in Theorem 56. Thus, suppose we are given a graph G = G^{n} and a (ϱ, A)-uniform graph J = J^{n} on the same vertex set, say V, and suppose further that G satisfies property P_{J,△}(ε′), where 0 < ε′ ≤ ε_{0}, and r = ϱn ≥ r_{0}. We have to show that G is (1/2, ε, δ)-quasi-random.

In what follows, we assume that two disjoint sets U, W ⊂ V with |U|, |W | ≥ δn are given. We wish to show that inequality (96) holds. The approach we take is similar in spirit to the one used in the proof of Theorem 41.

Let A = (a_{ij})_{i,j∈V} be the adjacency matrix of G with entries in {±1}, with a_{ij} = 1 if ij ∈ G and a_{ij} = −1 if ij ∉ G. Let us write v_{i} = (a_{ij})_{j∈V} (i ∈ V) for the ith row of A. We start by observing that property P_{J,△}(ε′) implies that ∑_{ij∈J} | ⟨v_{i}, v_{j}⟩ | is small. Lemma 62. We have

∑_{ij∈J} |⟨v_{i}, v_{j}⟩| ≤ ε′ne(J).  (110)

Proof. By the definition of the v_{i}, we have

⟨v_{i}, v_{j}⟩ = n − 2|Γ_{G}(i) △ Γ_{G}(j)|,

and the result follows from the definition of property P_{J,△}(ε′). □

Our aim now is to estimate the left-hand side of (110) from below. It turns out that one may give a good lower bound for this quantity in terms of the number of G-edges e_{G}(U, W) between U and W ⊂ V for any pair (U, W) as long as both U and W are large enough.

Recall that sets U, W ⊂ V with u = |U|, w = |W | ≥ δn are fixed, and put w_{i} = (a_{ij})_{j∈W} for all i ∈ U. Thus, w_{i} is the restriction of v_{i} to the coordinates in W. For convenience, we shall write ∑_{ij∈J}^{U} to indicate sum over all edges ij ∈ J with both i and j in U.

Let us compare ∑_{ij∈J}^{U} ⟨v_{i}, v_{j}⟩ and ∑_{ij∈J}^{U} ⟨w_{i}, w_{j}⟩. Clearly,

∑_{ij∈J}^{U} ⟨v_{i}, v_{j}⟩ = ∑_{ij∈J}^{U} ⟨w_{i}, w_{j}⟩ + ∑_{k∈V \W} ∑_{ij∈J}^{U} a_{ik}a_{jk}.  (111)

In the lemma below, we estimate S_{k}^{U} = ∑_{ij∈J}^{U} a_{ik}a_{jk} for all k ∈ V. Recall that we write O_{1}(x) for any term y satisfying |y| ≤ x. Lemma 63. Fix a vertex k ∈ V, and let u = |U|, u^{+} = u_{k}^{+} = |Γ_{G}(k) ∩ U|, and u^{−} = u_{k}^{−} = |U \ Γ_{G}(k)|. Then

S_{k}^{U} = ∑_{ij∈J}^{U} a_{ik}a_{jk} = \frac{1}{2}ϱ ((u^{+} − u^{−})^{2} − u) + O_{1} (\frac{3}{2}Au\sqrt{r}) .  (112)

In particular, we have

S_{k}^{U} ≥ \frac{1}{2}ϱ(u^{+} − u^{−})^{2} − 2Au\sqrt{r} ≥ −2Au\sqrt{r}.  (113)

Proof. Note that an edge ij ∈ J contributes +1 to the sum in (112) if i, j ∈ Γ_{G}(k) ∩ U or else i, j ∈ U \ Γ_{G}(k). Similarly, the edge ij ∈ J contributes −1 to that sum if ij ∈ E(Γ_{G}(k) ∩ U, U \ Γ_{G}(k)).

By the (ϱ, A)-uniformity of J (see also (98) in Fact 53), we have

S_{k}^{U} = ∑_{ij∈J}^{U} a_{ik}a_{jk}

= ϱ\binom{u^{+}}{2} + O_{1} (Au^{+}\sqrt{r})

+ ϱ\binom{u^{−}}{2} + O_{1} (Au^{−}\sqrt{r}) − ϱu^{+}u^{−} + O_{1} (A\sqrt{ru^{+}u^{−}})

= ϱ (\frac{1}{2}(u^{+})^{2} + \frac{1}{2}(u^{−})^{2} − u^{+}u^{−} − \frac{1}{2}(u^{+} + u^{−}))

+ O_{1} (A\sqrt{r}(u^{+} + u^{−} + \sqrt{u^{+}u^{−}})) ,

from which (112) follows.

Since A ≥ 1 and r < n, we have ϱu/2 ≤ (1/2)Au\sqrt{r}. Therefore, the right-hand side of (112) is at least

\frac{1}{2}ϱ(u^{+} − u^{−})^{2} − \frac{1}{2}ϱu − \frac{3}{2}Au\sqrt{r} > \frac{1}{2}ϱ(u^{+} − u^{−})^{2} − 2Au\sqrt{r}.  (114)

Inequality (113) follows from (114) and Lemma 63 is proved. □

An immediate corollary to (111) and (113) is that

∑_{ij∈J}^{U} ⟨v_{i}, v_{j}⟩ ≥ ∑_{ij∈J}^{U} ⟨w_{i}, w_{j}⟩ − 2A(n − w)u\sqrt{r},  (115)

where, as before, w = |W |. We now estimate ∑_{ij∈J}^{U} ⟨w_{i}, w_{j}⟩ from below using Lemma 63. Put

u_{∗}^{+} = Ave_{k∈W} u_{k}^{+} = Ave_{k∈W} |Γ_{G}(k) ∩ U| = \frac{1}{w} e_{G}(U, W),  (116)

where Ave_{k∈W} denotes average over all k ∈ W.

Lemma 64. We have

∑_{ij∈J}^{U} ⟨w_{i}, w_{j}⟩ ≥ \frac{1}{2}ϱw(2u_{∗}^{+} − u)^{2} − 2Auw\sqrt{r}.  (117)

Proof. We make use of Lemma 63. We have u_{k}^{+} −u_{k}^{−} = 2u_{k}^{+} −u for all k. Therefore, inequality (113) in Lemma 63 tells us that

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

≥ \frac{1}{2}ϱ ∑_{k∈W}(u_{k}^{+} − u_{k}^{−})^{2} − 2Auw\sqrt{r}

= \frac{1}{2}ϱ ∑_{k∈W}(2u_{k}^{+} − u)^{2} − 2Auw\sqrt{r},

which, by convexity (or Cauchy–Schwarz), is at least as large as the right-hand side of (117). The proof of this lemma is complete. □

We now put Lemmas 62 and 64 and inequality (115) together to obtain

\frac{1}{2}ϱw(2u_{∗}^{+} − u)^{2} − 2Aun\sqrt{r} ≤ ∑_{ij∈J}^{U} ⟨w_{i}, w_{j}⟩ − 2Au(n − w)\sqrt{r}

≤ ∑_{ij∈J}^{U} ⟨v_{i}, v_{j}⟩ ≤ ∑_{ij∈J}^{U} |⟨v_{i}, v_{j}⟩| ≤ ∑_{ij∈J} |⟨v_{i}, v_{j}⟩| ≤ ε′ne(J). (118)

We now make use of (98) in Fact 53 to deduce that

e(J) ≤ ϱ\binom{n}{2} + An\sqrt{r} ≤ \frac{1}{2}rn + An\sqrt{r}.  (119)

Therefore

ε′ne(J) ≤ \frac{1}{2}ε′rn^{2} + ε′An^{2}\sqrt{r},  (120)

and hence (118) gives that

\frac{1}{2}ϱw(2u_{∗}^{+} − u)^{2} ≤ \frac{1}{2}ε′rn^{2} + ε′An^{2}\sqrt{r} + 2Aun\sqrt{r}.  (121)

However, we have

\frac{1}{2}ϱw(2u_{∗}^{+} − u)^{2} = \frac{1}{2}ϱw (\frac{2}{w} e_{G}(U, W) − u)^{2} = 2\frac{ϱ}{w} (e_{G}(U, W) − \frac{1}{2}uw)^{2} . (122)

From (121) and (122), we obtain

\begin{aligned}|e_{G}(U, W) − \frac{1}{2}uw|^{2} & ≤ \frac{1}{4ϱ}ε′rn^{2}w + \frac{1}{2ϱ}ε′An^{2}w\sqrt{r} + \frac{1}{ϱ}Auwn\sqrt{r} \\ & = \frac{1}{4}ε′n^{3}w + \frac{1}{2\sqrt{r}} ε′An^{3}w + \frac{1}{\sqrt{r}} Auwn^{2} \\ & = ε′n^{3}w (\frac{1}{4} + \frac{A}{2\sqrt{r}} ) + \frac{A}{\sqrt{r}} n^{2}uw. \end{aligned}  (123)

Using (107), (108), and (109) and the fact that ε′ ≤ ε_{0} and r ≥ r_{0}, we deduce that the last expression in (123) is at most

\frac{1}{2}ε′n^{3}w + \frac{1}{8}ε^{2}δ^{2}n^{2}uw ≤ \frac{1}{8}ε^{2}δ^{3}n^{3}w + \frac{1}{8}ε^{2}δ^{2}n^{2}uw

≤ \frac{1}{8}ε^{2}u^{2}w^{2} + \frac{1}{8}ε^{2}u^{2}w^{2} = (\frac{1}{2}εuw)^{2} . (124)

Putting together (123) and (124), we deduce inequality (96).

The proof of Theorem 56 is complete.

7.5. Proof of Theorem 57. Let constants 0 < γ ≤ 1, 0 < ε ≤ 1, and A ≥ 1 be given. Let us define the constants ε_{0} = ε_{0}(γ, ε, A), δ_{0} = δ_{0}(γ, ε, A), r_{1} = r_{1}(γ, ε, A), and N_{1} = N_{1}(γ, ε, A) as follows.

We start by putting

ε_{0} = ε_{0}(γ, ε, A) = \frac{1}{2^{6}} γε.  (125)

The definitions of δ_{0} and r_{1} are a little more elaborate. Let

ε′′ = \frac{1}{2^{6}} γε ≤ \frac{1}{2^{6}}  (126)

and

k_{0} = ⌈\frac{2^{6}}{γε}⌉ ,  (127)

and put D = 2. Let

η = η(ε′′, k_{0}, D) > 0 and K_{0} = K_{0}(ε′′, k_{0}, D) ≥ k_{0},  (128)

and N_{0} = N_{0}(ε′′, k_{0}, D) be the constants whose existence is guaranteed by Theorem 15 for ε′′, k_{0}, and D = 2. We may clearly assume that

K_{0} ≥ \frac{1}{2ε′′} .  (129)

We now let

δ_{0} = δ_{0}(γ, ε, A) = min \{\frac{1}{2^{7}} γε, \frac{1}{2K_{0}} \} ,  (130)

and let

r_{1} = r_{1}(γ, ε, A) = max \{(2AK_{0})^{2}, (\frac{A}{η})^{2}\}  (131)

and

N_{1} = N_{1}(γ, ε, A) = N_{0}(ε′′, k_{0}, D).  (132)

We claim that these choices for ε_{0}, δ_{0}, r_{1}, and N_{1} will do in Theorem 57. However, before we start the proof of this claim, let us observe that the constants above obey the following ‘hierarchy’:

δ_{0} ≪ \frac{1}{K_{0}} ≤ \frac{1}{k_{0}} ≪ γε  (133)

and

ε_{0}, ε′′ ≤ γε.  (134)

Moreover,

r_{1} ≫ A, K_{0}, \frac{1}{η}  (135)

so that, in a (ϱ, A)-uniform graph J = J^{n}, the number of edges between two disjoint sets of vertices U and W ⊂ V (J) is roughly equal to the expected quantity ϱ|U||W |, as long as

|U|, |W | ≥ n min \{\frac{1}{2K_{0}} , η\}  (136)

(see the proof of (139) below for details). The reader may find it useful to keep in mind the above relationship among our constants.

We now start with the proof that the above choices for ε_{0}, δ_{0}, r_{1}, and N_{1} work. Let a (ϱ, A)-uniform graph J = J^{n} with n ≥ N_{1} vertices be fixed and let G be a (1/2, ε′, δ′)-quasi-random graph on V = V (J), where 0 < ε′ ≤ ε_{0}, 0 < δ′ ≤ δ_{0}, and r ≥ r_{1}. We shall prove that G has property P′_{J,△}(γ, ε).

Assume for a contradiction that P′_{J,△}(γ, ε) fails for G. Therefore we know that the number of edges ij ∈ J in J that violate inequality (100) is greater than γe(J). Let us assume that the number of edges ij ∈ J for which we have

|Γ_{G}(i) △ Γ_{G}(j)| − \frac{1}{2}n < −\frac{1}{2}εn  (137)

is larger than (γ/2)e(J). The case in which

|Γ_{G}(i) △ Γ_{G}(j)| − \frac{1}{2}n > \frac{1}{2}εn  (138)

occurs for more than (γ/2)e(J) edges ij of J is analogous. We let H be the graph on V = V (J) whose edges are the edges ij ∈ J that satisfy (137).

The regularity lemma for sparse graphs implies Lemma 65 below. We shall use the second form of the lemma, Theorem 15, although the first version, Theorem 13, would equally do (with the first version the calculations involved would be slightly longer). Lemma 65. The graph H contains an (ε′′, H, ϱ)-regular pair (U, W) of ϱ-density d_{H,ϱ}(U, W) at least γ/4 and with |U| = |W | = m ≥ n/2K_{0}.

Proof. Let η_{0} = min{1/2K_{0}, η}, where η and K_{0} are as defined in (128). We claim that H = H^{n} is an (η_{0}, 2)-upper-uniform graph with respect to density ϱ, that is, if U, W ⊂ V = V (H) are disjoint and |U|, |W | ≥ η_{0}n, then

e_{H}(U, W) ≤ 2ϱ|U||W |.

Because of the (ϱ, A)-uniformity of J ⊃ H, it suffices to check that

A\sqrt{r|U||W |} ≤ ϱ|U||W |  (139)

(see (97)). However, this follows easily from (131) and the fact that r = ϱn ≥ r_{1}.

Having verified that H is (η_{0}, 2)-upper-uniform with respect to density ϱ, we may invoke Theorem 15 to obtain an (ε′′, H, ϱ)-regular (ε′′, k)-equitable partition (C_{i})_{0}^{k} of the vertex set of H with k_{0} ≤ k ≤ K_{0}. Observe that

|C_{i}| ≥ \frac{n}{2K_{0}} for all 1 ≤ i ≤ k,  (140)

since |C_{0}| ≤ ε′′n < n/2 (see (126)). We shall now apply a standard argument to show that we may take for (U, W) some pair (C_{i}, C_{j}). We already know from (140) that the C_{i} (1 ≤ i ≤ k) have large enough cardinality. Put m = |C_{i}| (1 ≤ i ≤ k) and observe that

\frac{n}{2K_{0}} ≤ m ≤ \frac{n}{k}.  (141)

It suffices to prove the following claim to complete the proof of Lemma 65.

Claim 66. There exist 1 ≤ i < j ≤ k for which the pair (C_{i}, C_{j}) is (ε′′, H, ϱ)-regular and d_{H,ϱ}(C_{i}, C_{j}) ≥ γ/4.

Proof. Suppose for a contradiction that no pair (C_{i}, C_{j}) with 1 ≤ i < j ≤ k is good. Working under this hypothesis, we shall deduce that the number of edges in H is at most (γ/2)e(J), which will contradict the definition of the graph H.

Let us turn to the estimation of e(H). There are four types of edges in H:

(i) edges that are induced by (ε′′, H, ϱ)-regular pairs (C_{i}, C_{j}) with 1 ≤ i < j ≤ k, (ii) edges that are induced by (ε′′, H, ϱ)-irregular pairs (C_{i}, C_{j}) with 1 ≤ i < j ≤ k, (iii) edges that are induced within the classes C_{i} (1 ≤ i ≤ k), that is, edges in ⋃_{1≤i≤k} H[C_{i}], and (iv) edges that are incident to the exceptional class C_{0}. We now estimate the number of edges of each type in turn.

Because of our assumption that no pair (C_{i}, C_{j}) will do for our claim, all the (ε′′, H, ϱ)-regular pairs (C_{i}, C_{j}) with 1 ≤ i < j ≤ k are such that

d_{H,ϱ}(U, W) = \frac{e_{H}(U, W)}{ϱ|U||W |} < \frac{γ}{4} .  (142)

Thus, the number of edges of type (i) is

< \frac{γ}{4} ϱm^{2}\binom{k}{2} ≤ \frac{γ}{4} ϱ (\frac{n}{k})^{2} \frac{k^{2}}{2} = \frac{γ}{4} (ϱ\frac{n^{2}}{2} ) .  (143)

We know that H is a (η_{0}, 2)-upper-uniform graph with respect to density ϱ, and that the C_{i} (1 ≤ i ≤ k) have cardinality m ≥ (1/2K_{0})n ≥ η_{0}n. Therefore the number of edges induced by a pair (C_{i}, C_{j}) with 1 ≤ i < j ≤ k is at most 2ϱm^{2}. We also know that the number of (ε′′, H, ϱ)-irregular pairs is at most ε′′\binom{k}{2}, and hence we deduce that the number of edges of type (ii) is, by (126),

≤ 2ϱm^{2}ε′′\binom{k}{2} ≤ 2ε′′ϱ (\frac{n}{k})^{2} \frac{k^{2}}{2} ≤ \frac{γ}{2^{5}} (\frac{1}{2}ϱn^{2}) .  (144)

Fact 53 together with the fact that Am\sqrt{r} ≤ ϱm^{2} (cf. (139)) imply that e(H[C_{i}]) ≤ (3/2)ϱm^{2}. Therefore, the number of edges of type (iii) is, by (127),

≤ \frac{3}{2}ϱm^{2}k ≤ \frac{3}{2}ϱ (\frac{n}{k})^{2} k = \frac{3}{k} (ϱ\frac{n^{2}}{2} ) ≤ \frac{3}{2^{6}} γ (\frac{1}{2}ϱn^{2}) .  (145)

We now observe that, because of (129), we have ε′′ ≥ 1/2K_{0} ≥ η_{0}. Therefore, the number of edges of type (iv), that is, incident to C_{0}, is, by (126),

≤ \frac{3}{2}ϱ(ε′′n)^{2} + 2ϱε′′n^{2} = (3(ε′′)^{2} + 4ε′′) ϱ\frac{n^{2}}{2} ≤ \frac{5}{2^{6}} γ (\frac{1}{2}ϱn^{2}) .  (146)

We conclude from (143)–(146) that the number of edges in H satisfies

e(H) ≤ (\frac{1}{2^{2}} + \frac{1}{2^{5}} + \frac{1}{2^{3}} ) γ (\frac{1}{2}ϱn^{2}) < \frac{7}{16}γ (\frac{1}{2}ϱn^{2}) .  (147)

We shall now estimate e(J) from below. Fact 53 tells us that

e(J) ≥ ϱ\binom{n}{2} − An\sqrt{r} = \frac{1}{2}ϱn^{2} − \frac{1}{2}ϱn − An\sqrt{r} = \frac{1}{2}ϱn^{2} − \frac{r}{2} − An\sqrt{r}. (148)

Using that n ≥ N_{1} ≥ 16, we obtain r/2 ≤ (1/16)ϱn^{2}/2, and using that r ≥ r_{1} ≥ (2AK_{0})^{2} ≥ (2Ak_{0})^{2} > (2^{5}A)^{2}, we obtain that An\sqrt{r} ≤ (1/16)ϱn^{2}/2. We therefore conclude from (148) that

e(J) ≥ \frac{7}{8} (\frac{1}{2}ϱn^{2}) .  (149)

Finally, (147) and (149) imply that e(H) < (γ/2)e(J), which is a contradiction. Therefore some pair (C_{i}, C_{j}) must be as required, and the proof of Claim 66 is complete. □

We now fix a pair (C_{i}, C_{j}) as in Claim 66, and let U = C_{i} and W = C_{j}. Recalling (140), we see that the pair (U, W) is as required in Lemma 65, and hence we are done. □

We now restrict our attention to the pair (U, W) given by Lemma 65. We shall in fact obtain a contradiction by estimating from above and from below the quantity

|∑_{ij∈H}^{(U,W)} ⟨v_{i}, v_{j}⟩| ,  (150)

where ∑_{ij∈H}^{(U,W)} denotes sum over all edges ij ∈ H with i ∈ U and j ∈ W. (The number of summands in (150) is, therefore, e_{H}(U, W).)

We start by noticing that we have the following lower bound for (150) from the definition of the edge set of H and the fact that (U, W) is a ‘dense’ pair for H. Lemma 67. We have

|∑_{ij∈H}^{(U,W)} ⟨v_{i}, v_{j}⟩| > \frac{1}{4}εγnϱm^{2}.  (151)

Proof. For any ij ∈ H, by (137), we have

⟨v_{i}, v_{j}⟩ = n − 2|Γ_{G}(i) △ Γ_{G}(j)| > n − 2 (\frac{1}{2}n − \frac{1}{2}εn) = εn.

Therefore, we have

∑_{ij∈H}^{(U,W)} ⟨v_{i}, v_{j}⟩ > εne_{H}(U, W) ≥ \frac{1}{4}ϱεγnm^{2},

since d_{H,ϱ}(U, W) ≥ γ/4 and hence e_{H}(U, W) ≥ (1/4)γϱm^{2}. Inequality (151) is proved. □

Remark 68. In the case in which H is the graph with edges ij for which (138) holds instead of (137), we have

⟨v_{i}, v_{j}⟩ = n − 2|Γ_{G}(i) △ Γ_{G}(j)| < n − 2 (\frac{1}{2}n + \frac{1}{2}εn) = −εn.

Therefore, we would have

∑_{ij∈H}^{(U,W)} ⟨v_{i}, v_{j}⟩ < −εne_{H}(U, W) ≤ −\frac{1}{4}ϱεγnm^{2},

and (151) would follow as well. For the remainder of the proof, it will not matter whether the edges of H satisfy (137) or (138). We shall only make use of (151).

Our upper bound for (150) will come from the (1/2, ε′, δ′)-quasi-randomness of G and the (ε′′, H, ϱ)-regularity of the pair (U, W). More specifically, we let

S_{k}^{(U,W)} = ∑_{ij∈H}^{(U,W)} a_{ik}a_{jk}  (152)

for all k ∈ V, and show that this sum is essentially always small, which will tell us that ∑_{ij∈H}^{(U,W)} ⟨v_{i}, v_{j}⟩ = ∑_{k∈V} S_{k}^{(U,W)} is quite small.

Let a vertex k ∈ V be given. We then let

U^{+} = U_{k}^{+} = Γ_{G}(k) ∩ U  U^{−} = U_{k}^{−} = U \ Γ_{G}(k)  (153)
W^{+} = W_{k}^{+} = Γ_{G}(k) ∩ W  W^{−} = W_{k}^{−} = W \ Γ_{G}(k).  (154)

Then, clearly,

S_{k}^{(U,W)} = e_{H}(U^{+}, W^{+}) + e_{H}(U^{−}, W^{−}) − e_{H}(U^{+}, W^{−}) − e_{H}(U^{−}, W^{+}). (155)

Moreover, for most k ∈ V, we may estimate the four terms on the right-hand side of (155) by ∼ d_{H,ϱ}(U, W)m^{2}/4.

Indeed, let us say that a vertex k ∈ V \ (U ∪ W) is (U, W)-typical, or simply typical, if

|U^{+}|, |U^{−}|, |W^{+}|, |W^{−}| = \frac{1}{2}(1 + O_{1}(ε′))m ≥ ε′′m.  (156)

Then, by the (ε′′, H, ϱ)-regularity of the pair (U, W), we have

e_{H}(U^{+}, W^{+}), e_{H}(U^{−}, W^{−}), e_{H}(U^{+}, W^{−}), e_{H}(U^{−}, W^{+}) ∼ \frac{1}{4}d_{H,ϱ}(U, W)m^{2}

(157)

for any typical k. Let us make this remark more precise. For simplicity, let us write σ = d_{H,ϱ}(U, W), and u^{+} = u_{k}^{+} = |U^{+}|, u^{−} = u_{k}^{−} = |U^{−}| and similarly for w^{+} and w^{−}.

Because r ≥ r_{1} ≥ (2AK_{0})^{2}, the graph H = H^{n} is a (1/2K_{0}, 2)-upper-uniform graph with respect to density ϱ (cf. the proof of Lemma 65). Therefore, we have

σ = d_{H,ϱ}(U, W) ≤ 2,  (158)

since |U|, |W | ≥ (1/2K_{0})n.

From (156) and the (ε′′, H, ϱ)-regularity of (U, W), we have

e_{H}(U^{α}, W^{β}) = (σ + O_{1}(ε′′)) ϱu^{α}w^{β},  (159)

for all α, β ∈ {+, −}. In particular, if we know that k is typical, we have

e_{H}(U^{+}, W^{+}), e_{H}(U^{−}, W^{−}) ≤ (σ + ε′′)ϱ \{\frac{1}{2}(1 + ε′)m\}^{2}  (160)

and

e_{H}(U^{+}, W^{−}), e_{H}(U^{−}, W^{+}) ≥ (σ − ε′′)ϱ \{\frac{1}{2}(1 − ε′)m\}^{2} .  (161)

A little computation now gives the first statement in the following lemma. The second statement is immediate. Lemma 69. (i) For any (U, W)-typical vertex k ∈ V \ (U ∪ W), we have

|S_{k}^{(U,W)}| = |∑_{ij∈H}^{(U,W)} a_{ik}a_{jk}| ≤ 2ϱm^{2}(ε′σ + ε′′).  (162)

(ii) For any vertex k ∈ V, we have

|S_{k}^{(U,W)}| = |∑_{ij∈H}^{(U,W)} a_{ik}a_{jk}| ≤ ϱm^{2} + Am\sqrt{r}.  (163)

Proof. Let us prove (i). Let a (U, W)-typical vertex k be fixed. Using (155), (160), and (161), we obtain

S_{k}^{(U,W)} = ∑_{ij∈H}^{(U,W)} a_{ik}a_{jk}

≤ (σ + ε′′)ϱu^{+}w^{+} + (σ + ε′′)ϱu^{−}w^{−}

− (σ − ε′′)ϱu^{+}w^{−} − (σ − ε′′)ϱu^{−}w^{+}

≤ 2(σ + ε′′)ϱ \{\frac{1}{2}(1 + ε′)m\}^{2} − 2(σ − ε′′)ϱ \{\frac{1}{2}(1 − ε′)m\}^{2}

= \frac{1}{2}(σ + ε′′)ϱ (1 + 2ε′ + (ε′)^{2}) m^{2} − \frac{1}{2}(σ − ε′′)ϱ (1 − 2ε′ + (ε′)^{2}) m^{2}

= \frac{1}{2}σϱm^{2}(4ε′) + \frac{1}{2}ε′′ϱm^{2}(2 + 2(ε′)^{2})

= \frac{1}{2}ϱm^{2}(4ε′σ + ε′′(2 + 2(ε′)^{2}))

≤ 2ϱm^{2}(ε′σ + ε′′),

and (i) is proved. To prove (ii) it suffices to recall that H ⊂ J and that J is a (ϱ, A)-uniform graph, and hence

|S_{k}^{(U,W)}| = |∑_{ij∈H}^{(U,W)} a_{ik}a_{jk}| ≤ e_{H}(U, W) ≤ e_{J}(U, W) ≤ ϱm^{2} + Am\sqrt{r}, (164)

as required. □

Our next lemma gives an upper bound for the quantity in (150). The reader will immediately see that this upper bound is a consequence of Lemma 69 and the fact that there are only very few atypical vertices k, because of the (1/2, ε′, δ′)-quasi-randomness of G. Lemma 70. We have

|∑_{ij∈H}^{(U,W)} ⟨v_{i}, v_{j}⟩| ≤ 2(2δ′n + m) (ϱm^{2} + Am\sqrt{r}) + 2ϱm^{2}n (ε′σ + ε′′) . (165)

Proof. We claim that the number of vertices k ∈ V \ (U ∪ W) that are not (U, W)- typical is, by the (1/2, ε′, δ′)-quasi-randomness of G, less than 4δ′n. Indeed, if we had ≥ 4δ′n vertices that are not (U, W)-typical, then we would have ≥ 2δ′n vertices that are not ‘typical’ for either U alone or else for W alone. In other words, we would have ≥ 2δ′n vertices k ∈ V \ (U ∪ W) for which, say,

|Γ_{G}(k) ∩ U| = |U^{+}| > \frac{1}{2}(1 + ε′)m  (166)

and hence |U \ Γ_{G}(k)| = |U^{−}| < (1/2)(1 − ε′)m, or else we would have ≥ 2δ′n vertices k ∈ V \ (U ∪ W) for which we have

|Γ_{G}(k) ∩ U| = |U^{+}| < \frac{1}{2}(1 − ε′)m  (167)

and hence |U \ Γ_{G}(k)| = |U^{−}| > (1/2)(1 + ε′)m. Therefore there would be ≥ δ′n vertices k ∈ V \ (U ∪ W) for which, say, (166) holds. Let T ⊂ V \ (U ∪ W) be the set of such vertices k. Then

|T | ≥ δ′n  (168)

and

e(T, U) > \frac{1}{2}(1 + ε′)|T |m = \frac{1}{2}(1 + ε′)|T ||U|.  (169)

We also have

|U| = m ≥ \frac{n}{2K_{0}} ≥ δ_{0}n ≥ δ′n  (170)

(see (130)). Inequalities (168)–(170) say that the pair (T, U) is a witness against the (1/2, ε′, δ′)-quasi-randomness of G. This contradiction confirms that, indeed, the number of vertices k ∈ V \(U ∪W) that are not (U, W)-typical is less than 4δ′n.

Using (162) for the (U, W)-typical vertices k ∈ V \ (U ∪ W), and using (163) for the vertices k ∈ V \ (U ∪ W) that are not (U, W)-typical and for all the vertices k ∈ U ∪ W, we have

|∑_{ij∈H}^{(U,W)} ⟨v_{i}, v_{j}⟩| = |∑_{k∈V} ∑_{ij∈H}^{(U,W)} a_{ik}a_{jk}| = |∑_{k∈V} S_{k}^{(U,W)}|

≤ (4δ′n + 2m) (ϱm^{2} + Am\sqrt{r}) + 2ϱm^{2}n (ε′σ + ε′′) ,

as required. □

We finish the proof by deriving a contradiction comparing Lemmas 67 and 70. To that end, we first claim that

\frac{1}{8}γε > 2 (2δ_{0} + \frac{1}{k_{0}} ) + ε_{0}σ + ε′′ ≥ 2 (2δ′ + \frac{1}{k_{0}} ) + ε′σ + ε′′.  (171)

To prove our claim, we first observe that, because δ′ ≤ δ_{0} and ε′ ≤ ε_{0}, the second inequality in (171) is obvious. As to the first inequality in (171), observe that, because of (130), we have

4δ_{0} ≤ \frac{1}{2^{5}} γε.  (172)

Moreover, because of (127), we have

\frac{2}{k_{0}} ≤ \frac{1}{2^{5}} γε.  (173)

Since σ ≤ 2 (see (158)), we have from (125) that

ε_{0}σ ≤ \frac{1}{2^{5}} γε.  (174)

Inequalities (172)–(174) and (126) imply the first inequality in (171).

We now recall inequalities (151) and (165) to obtain that

\frac{1}{4}εγnϱm^{2} < |∑_{ij∈H}^{(U,W)} ⟨v_{i}, v_{j}⟩|

≤ 2(2δ′n + m) (ϱm^{2} + Am\sqrt{r}) + 2ϱm^{2}n (ε′σ + ε′′) . (175)

Let us also recall that

Am\sqrt{r} ≤ ϱm^{2},  (176)

because r = ϱn ≥ r_{1} ≥ (2AK_{0})^{2} and m ≥ (1/2K_{0})n. Moreover, the fact that m ≤ n/k gives us that

2δ′n + m ≤ (2δ′ + \frac{1}{k} ) n ≤ (2δ′ + \frac{1}{k_{0}} ) n.  (177)

Inequalities (175), (176), and (140) give that

\frac{1}{4}εγnϱm^{2} ≤ 4(2δ′n + m)ϱm^{2} + 2ϱm^{2}n (ε′σ + ε′′)

≤ 4 (2δ′ + \frac{1}{k_{0}} ) ϱnm^{2} + 2ϱm^{2}n (ε′σ + ε′′) . (178)

Dividing (178) by 2ϱm^{2}n, we obtain

\frac{1}{8}εγ ≤ 2 (2δ′ + \frac{1}{k_{0}} ) + ε′σ + ε′′,  (179)

which contradicts (171).

The proof of Theorem 57 is complete.

References

1. N. Alon, Expanders, sorting in rounds and superconcentrators of limited depth, Proceedings of the 17th Annual ACM Symposium on the Theory of Computing (STOC 85), 1985, pp. 98–102. 1

2. , Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory, Combinatorica 6 (1986), no. 3, 207–219. 1

3. N. Alon, M.R. Capalbo, Y. Kohayakawa, V. Rödl, A. Ruciński, and E. Szemerédi, Universality and tolerance (extended abstract), Proceedings of the 41st IEEE Annual Symposium on Foundations of Computer Science (FOCS 2000), 2000, pp. 14–21. 1, 6.5

4. 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. 1, 6.4, 6.4, 6.4.1, 6.4.1

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

6. N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy, Efficient testing of large graphs, submitted, 22pp., 1999. 4.2, 4.2.1, 4.2.1, 4.2.2, 4.2.2, 4.2.2

7. , 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.2, 4.2.1, 4.2.1, 4.2.2, 4.2.2, 4.2.2

8. N. Alon and J. Spencer, The probabilistic method, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, New York, 1992. 3.2.3 9. Noga Alon and Raphael Yuster, H-factors in dense graphs, Journal of Combinatorial Theory,

Series B 66 (1996), no. 2, 269–282. 4.1

10. László Babai, Péter Frankl, and János Simon, Complexity classes in communication complexity theory (preliminary version), 27th Annual Symposium on Foundations of Computer Science (Toronto, Ontario, Canada), IEEE, 1986, pp. 337–347. 1

11. Béla Bollobás, Extremal graph theory, Academic Press Inc. [Harcourt Brace Jovanovich Publishers], London, 1978. 3.2

12. , Graph theory, Springer-Verlag, New York, 1979, An introductory course. 5, 2.2

13. , Random graphs, Academic Press Inc. [Harcourt Brace Jovanovich Publishers], London, 1985. 5, 2.2

14. , Modern graph theory, Springer-Verlag, New York, 1998. 5, 2.2

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

16. V. Chvátal, V. Rödl, E. Szemerédi, and W. T. Trotter, The Ramsey number of a graph with bounded maximum degree, Journal of Combinatorial Theory, Series B 34 (1983), no. 3, 239–243. 4.1

17. Don Coppersmith and Shmuel Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput. 9 (1990), no. 3, 251–280. 1, 6.4

18. W. Deuber, A generalization of Ramsey’s theorem, Infinite and Finite Sets (Keszthely, 1973) (A. Hajnal, R. Rado, and V. T. Sós, eds.), Colloquia Mathematica Societatis János Bolyai, vol. 10, North-Holland, 1975, pp. 323–332. 3.2.2

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

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

21. P. Erdős, A. Hajnal, and L. Pósa, Strong embeddings of graphs into colored graphs, Infinite and Finite Sets (Keszthely, 1973) (A. Hajnal, R. Rado, and V. T. Sós, eds.), Colloquia Mathematica Societatis János Bolyai, vol. 10, North-Holland, 1975, pp. 585–595. 3.2.2

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

23. Paul Erdős, Some old and new problems in various branches of combinatorics, Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979) (Winnipeg, Man.), Utilitas Math., 1979, pp. 19–37. 3.2

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

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

26. P. Frankl, V. Rödl, and R. M. Wilson, The number of submatrices of a given type in a Hadamard matrix and related results, J. Combin. Theory Ser. B 44 (1988), no. 3, 317–328. 1, 3.2.3

27. 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. 6.4

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

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

30. 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. 4.2.1, 4.2.1

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

32. Oded Goldreich and Dana Ron, Property testing in bounded degree graphs, 29th ACM Symposium on Theory of Computing (El Paso, Texas), 1997, pp. 406–419. 4.2.1 33. , A sublinear bipartiteness tester for bounded degree graphs, Combinatorica 19 (1999),

no. 3, 335–373. 4.2.1

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

35. Svante Janson, Tomasz Łuczak, and Andrzej Rucinski, Random graphs, Wiley-Interscience, New York, 2000. 5, 2.2

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

37. Y. Kohayakawa and V. Rödl, Algorithmic aspects of regularity, LATIN’2000: Theoretical Informatics (Punta del Este, 2000) (G. Gonnet, D. Panario, and A. Viola, eds.), Lecture Notes in Computer Science, Springer, Berlin, 2000, pp. 1–17. 1, 6.4

38. , Regular pairs in sparse random graphs I, submitted, 2001. 1, 6.5

39. , Regular pairs in sparse random graphs II, in preparation, 2001. 1

40. Y. Kohayakawa, V. Rödl, and E. Szemerédi, The size-Ramsey number of graphs of bounded degree, in preparation, 2001. 6.5

41. Y. Kohayakawa, V. Rödl, and L. Thoma, On checking regularity, in preparation, 2001. 1, 6.4, 7, 7.3

42. 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. 1

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

44. János Komlós, Gábor N. Sárközy, and Endre Szemerédi, Proof of a packing conjecture of Bollobás, Combin. Probab. Comput. 4 (1995), no. 3, 241–255. 4.1

45. , Blow-up lemma, Combinatorica 17 (1997), no. 1, 109–123. 4.1

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

47. , On the Pósa-Seymour conjecture, J. Graph Theory 29 (1998), no. 3, 167–176. 4.1 48. , Proof of the Seymour conjecture for large graphs, Ann. Comb. 2 (1998), no. 1, 43–60.

4.1

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

50. 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. 7.3

51. , Ramanujan graphs, Combinatorica 8 (1988), 261–277. 7.3

52. Jaroslav Nešetřil and Vojtěch Rödl, Partition theory and its application, Surveys in combinatorics (Proc. Seventh British Combinatorial Conf., Cambridge, 1979), Cambridge Univ. Press, Cambridge, 1979, pp. 96–156. 3.2.2

53. V. Nikiforov, On a problem of Erdős about the local density of K_{p}-free graphs, submitted, 1999. 3.2

54. V. Rödl, The dimension of a graph and generalized Ramsey theorems, Master’s thesis, Charles University, 1973. 3.2.2

55. , On universality of graphs with uniformly distributed edges, Discrete Mathematics 59 (1986), no. 1-2, 125–134. 1, 3, 3.2

56. Vojtěch Rödl and Andrzej Ruciński, Perfect matchings in ε-regular graphs and the blow-up lemma, Combinatorica 19 (1999), no. 3, 437–452. 4.1

57. Vojtěch Rödl, Andrzej Ruciński, and Michelle Wagner, An algorithmic embedding of graphs via perfect matchings, Randomization and approximation techniques in computer science (Barcelona, 1998), Springer, Berlin, 1998, pp. 25–34. 4.1

58. Ronitt Rubinfeld and Madhu Sudan, Robust characterizations of polynomials with applications to program testing, SIAM Journal on Computing 25 (1996), no. 2, 252–271. 4.2.1

59. P. Sarnak, Some applications of modular forms, Cambridge University Press, Cambridge, 1990. 7.3 60. 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. 2.1, 2.1.2, 5.2, 5.2, 5.3

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

62. 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. 1, 3.2.3

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

64. P. Turán, Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok 48 (1941), 436–452, in Hungarian, with German summary. 3.3.2

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

   E-mail address: yoshi@ime.usp.br

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

   E-mail address: rodl@mathcs.emory.edu