REGULAR PAIRS IN SPARSE RANDOM GRAPHS I

Y. KOHAYAKAWA AND V. RÖDL

Dedicated to the memory of Professor Paul Erdős

Abstract. We consider bipartite subgraphs of sparse random graphs that are regular in the sense of Szemerédi and, among other things, show that they must satisfy a certain local pseudorandom property. This property and its consequences turn out to be useful when considering embedding problems in subgraphs of sparse random graphs.

Contents

1. Introduction 2 1.1. An equivalence result for regularity and an embedding lemma 3 1.2. Negative results for the sparse case 4 1.3. Positive results for the sparse case 5 1.3.1. A generalization of Theorem A′′ 7 1.3.2. The hereditary nature of ε-regularity 7 1.4. Applications 7 1.4.1. Random graphs and fault-tolerance 7 1.4.2. Extremal problems for subgraphs of random graphs 8 1.4.3. An application to Ramsey theory 9 1.5. The organization of this paper 10 1.6. Remarks on notation 11 2. Excluding counterexamples 11 3. Preliminary results 13 3.1. Preliminary definitions 13 3.2. A regularity lemma for sparse graphs 13 3.3. Further notation and definitions 14 3.4. Elementary lemmas on random graphs 15 3.4.1. The statement of the lemmas 15 3.4.2. Proofs of the elementary lemmas 16 3.5. Elementary tail inequalities 18 4. Regular pairs in sparse random graphs 20 4.1. The pair condition lemma 21 4.1.1. The statement of the lemma 21 4.1.2. Proof of the pair condition lemma 22 4.1.3. Proof of the pair condition lemma, r.gs version 29 4.2. A local condition for regularity 30 4.2.1. The statement of the lemma 30 4.2.2. Proof of the local condition lemma 31 4.2.3. Proof of the local condition lemma, r.gs version 34 4.3. The one-sided neighbourhood lemma 34 4.3.1. Statement of the one-sided neighbourhood lemma, auxiliary version 34 4.3.2. Statement of the one-sided neighbourhood lemma, counting version 36 4.3.3. Statement of the one-sided neighbourhood lemma, r.gs version 37 4.3.4. A two-sided neighbourhood lemma 38 4.3.5. Proof of the one-sided neighbourhood lemma, auxiliary version 39 4.3.6. Proof of the one-sided neighbourhood lemma, counting version 44 4.3.7. Proof of the one-sided neighbourhood lemma, r.gs version 46 4.4. The k-tuple lemma for subgraphs of random graphs 51 4.4.1. The statement of the k-tuple lemma 51 4.4.2. The proof of the k-tuple lemma 52 5. An example 57 5.1. The construction 57 References 61

Date: Copy produced on December 31, 2002.

1991 Mathematics Subject Classification. 05C80.

Key words and phrases. Random graphs, regular pairs, Szemerédi’s regularity lemma.

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.

The authors are grateful to the referee for his or her careful work and encouraging words.

1. Introduction

Many graph properties are shared by most graphs. A more formal way of stating this is to define a random graph, that is, a probability distribution over a suitable family of graphs, and then show that the probability of the events of interest tend to one as the order of the random graph tends to infinity. Typical properties of random graphs are deterministically equivalent in the sense that any large enough graph that satisfies one of these properties must satisfy all others as well. The equivalence of some of these properties was first proved by Thomason [47] and some other authors [2, 17, 36]. An important paper in this area is due to Chung, Graham, and Wilson [9], who systematized the theory and very clearly advocated the importance of the equivalence of many quite disparate quasirandom properties. Graphs with such properties are called quasirandom.

One may argue that quasirandom graphs are fundamental by relating them to a celebrated theorem of Szemerédi, namely, his beautiful regularity lemma [46]. Indeed, the regularity lemma states that the edge set of any graph can be decomposed into quasirandom induced bipartite subgraphs. In this context, quasirandom bipartite graphs are called ε-regular pairs. A wealth of material concerning the regularity lemma may be found in an excellent survey by Komlós and Simonovits [33].

Owing to the work of many authors, we may now say that the notion of quasirandomness applied to ‘dense’ graphs is quite well understood. Here, by a dense graph we mean a graph with ≥ cn^{2} edges, where c is any fixed positive constant, n is the number of vertices in the graph, and we consider n → ∞. The situation is different for the case of ‘sparse’ graphs, namely, graphs with o(n^{2}) edges. (See, however, Remark 3 in Section 1.2 below.) Our aim in this paper is to investigate the structure of sparse ε-regular pairs, with applications to the theory of random graphs in mind.

In the remainder of the introduction, we discuss some of the theorems that we prove in this paper, together with some other related facts. In Section 1.1, to motivate our results, we recall two well-known theorems concerning ‘dense’ regular pairs. In Section 1.2, we present two negative results that show that straightforward extensions to the sparse case of the two theorems in Section 1.1 do not hold. In Section 1.3, we state two positive results, Theorems A′′ and Theorem B′′: these results concern subgraphs of sparse random graphs and are our ‘sparse counterparts’ to the two theorems in Section 1.1. In this paper we focus on Theorem A′′ and some related results.

We conclude this somewhat long introduction with a discussion on some applications of Theorems A′′ and B′′, which will appear elsewhere.

1.1. An equivalence result for regularity and an embedding lemma. In this section, we discuss two well-known results concerning ε-regular pairs.

Fix 0 < p < 1 and let m be an integer. Let U and W be two disjoint sets with |U| = |W | = m. Consider the random bipartite graph G(m, m; p) on U ∪ W, in which the edges are chosen randomly and independently with probability p.

One can show that the following two properties are satisfied with probability tending to 1 as m → ∞.

(P_{1}) ∑_{u∈U} | deg(u)−pm| = o(m^{2}) and m^{−2} ∑_{u, u′∈U} | deg(u, u′)−p^{2}m| = o(m). Here, deg(u) and deg(u, u′) denote the number of neighbours of u (the degree of u) and the number of common neighbours of u and u′ (the joint degree or codegree of u and u′), respectively.

(P_{2}) For every U′ ⊂ U and W′ ⊂ W, the number e(U′, W′) of edges {u, w} ∈ G(m, m; p), with u ∈ U′ and w ∈ W′, satisfies e(U′, W′) = p|U′||W′| +

o(m^{2}).

It turns out that these properties (together with several others) are equivalent in the following deterministic sense. Theorem A (Equivalence lemma). For every ε > 0, there exist m_{0} and δ > 0 such that any bipartite graph G = (U, W; E) with |U| = |W | = m > m_{0} that satisfies one of properties P_{1} or P_{2} with o(m^{2}) replaced by ≤ δm^{2} must satisfy the other one with o(m^{2}) replaced by ≤ εm^{2}.

Theorem A, either in full or in part, and its variants have appeared in several papers, because of its basic nature; see, for example, [3, 4, 5, 9, 11, 17, 47, 48] and the upper bound in Theorem 15.2 in [15].

The importance of Theorem A comes from the fact that property P_{2} is in fact fundamental, as the next result shows. Let G = (V, E) be a graph and U, W ⊂ V a pair of disjoint sets of vertices. Denote by E(U, W) the set of all edges between U and W, i.e.,

E(U, W) = {{u, w}: u ∈ U, w ∈ W }.

The density of the pair (U, W) is defined by

d(U, W) = \frac{|E(U, W)|}{|U||W |}.  (1)

The pair (U, W) is called ε-regular if

|d(U, W) − d(U′, W′)| < ε  (2)

for any U′ ⊂ U and W′ ⊂ W with |U′| ≥ ε|U| and |W′| ≥ ε|W |. We may now state Szemerédi’s celebrated regularity lemma.

Theorem 1 (Szemerédi’s regularity lemma [46]). For every ε > 0 and k_{0} ≥ 1, there exists an integer K_{0} = K_{0}(ε, k_{0}) such that any graph G admits a partition V = V_{1} ∪ ⋯ ∪ V_{k}, where |V_{1}| ≤ |V_{2}| ≤ ⋯ ≤ |V_{k}| ≤ |V_{1}| + 1 and k_{0} ≤ k ≤ K_{0}, such that all but ≤ ε\binom{k}{2} pairs (V_{i}, V_{j}) are ε-regular.

In view of Theorem 1, we may say that bipartite graphs that satisfy property P_{2} in Theorem A are the building blocks for all graphs. This highlights the importance of property P_{2}.

Note that Theorem A, the equivalence lemma, tells us that the notion of εregularity is equivalent to a condition concerning global uniformity of degrees and codegrees. Since codegrees concern only pairs of vertices, and not large subsets U′ and W′ as in the definition of regularity, we have a ‘local’ criterion for regularity.

Remark 1 (Pair condition for regularity). We refer to the implication “P_{2} ⇒ P_{1}” as the pair condition for regularity, or PCR.

Remark 2 (Local condition for regularity). We refer to the implication “P_{1} ⇒ P_{2}” as the local condition for regularity, or LCR.

Let us now consider applications of the regularity lemma. The result below and its generalizations are crucial in the proofs of most of the applications of the regularity lemma. Theorem B (Embedding lemma). For every d > 0, there exist an ε > 0 and m_{0} ≥ 1 such that the following holds: let H be a graph with vertex set {1, …, k}. Let G = (V, E) be a graph and V_{1}, …, V_{k} be k disjoint subsets of V, with |V_{1}| = ⋯ = |V_{k}| = m ≥ m_{0}. If all pairs (V_{i}, V_{j}) with {i, j} ∈ E(H) are ε-regular with density ≥ d, then G contains a copy of H with vertex set {v_{1}, …, v_{k}}, with v_{i} ∈ V_{i} for all 1 ≤ i ≤ k.

It is quite natural to refer to results of the form of Theorem B as embedding lemmas. It turns out that one can in fact prove that the number of copies of the graph H in G in Theorem B is at least d^{|E(H)|}m^{k}(1 − g(ε)), where g(ε) → 0 as ε → 0. Such statements are sometimes referred to as counting lemmas.

1.2. Negative results for the sparse case. Let us now discuss two negative results that show that the results in Section 1.1 do not generalize to the sparse case. In order to deal with graphs with vanishing density, that is, o(n^{2}) edges, we need to redefine the concept of density.

Suppose we have a bipartite graph B = (V, E) with vertex partition V = U ∪W. Let T = |E| be the number of edges in B. We shall say that B is (ε, T)-regular if for all U′ ⊂ U and W′ ⊂ W with |U′| ≥ ε|U| and |W′| ⊂ ε|W |, we have

||E(U′, W′)| − \frac{|U′||W′|}{|U||W |}T | ≤ ε\frac{|U′||W′|}{|U||W |}T.  (3)

One’s hope to extend Theorem A, the equivalence lemma, to the ‘sparse’ case in a naïve way is dashed by the following result. Theorem A′ (Counterexample to PCR, sparse setting). For every 0 < α < 1 and 0 < ε < 1, there exist a constant 0 < p < 1 and an integer m_{0} ≥ 1 such that for every m > m_{0} there is a bipartite graph B with vertex classes U and W with |U| = |W | = m and with T edges such that

(i) B is (ε, T)-regular, (ii) (1 − ε)pm^{2} ≤ T ≤ (1 + ε)pm^{2},

but (iii) for all but ≤ αm^{2} pairs u_{1}, u_{2} ∈ U (u_{1} ≠ u_{2}), we have

deg(u_{1}, u_{2}) = 0 and consequently | deg(u_{1}, u_{2}) − d^{2}m| > εd^{2}m,  (4)

where d = T/m^{2} is the density of B. Recall that Theorem A, the equivalence lemma, is composed of the ‘pair condi-

tion for regularity’ (PCR) and the ‘local condition for regularity’ (LCR). Theorem A′ above tells us that a straightforward generalization of PCR does not hold in the sparse setting.

Theorem B, the embedding lemma, may not be extended to the sparse case in a straightforward way either, as the following result shows. Theorem B′ (Counterexample to the embedding lemma, sparse setting). For every 0 < ε < 1, there exist a constant 0 < p < 1 and an integer m_{0} ≥ 1 for which the following holds. For every m > m_{0}, there is a tripartite graph J with vertex classes V_{1}, V_{2}, and V_{3}, all of cardinality m, such that for all 1 ≤ i < j ≤ 3, the bipartite graph J_{ij} induced by V_{i} and V_{j} is such that

(i) J_{ij} has T = ⌊pm^{2}⌋ edges, (ii) J_{ij} is (ε, T)-regular,

but

(iii) J contains no triangle K^{3} as a subgraph.

Remark 3. In a recent paper, Chung and Graham [10] address thoroughly the problem of extending to the sparse case the well-known notion of quasirandomness of graphs, as developed in Chung, Graham, and Wilson [9]. In particular, Chung and Graham [10] investigate the problem of extending embedding lemmas to the sparse setting.

We remark that Thomason [47, 48] did prove embedding lemmas for sparse graphs, starting from natural, but stronger, pseudorandom hypotheses. Although we do not make this precise, we mention that the approach taken in [10] is different from the approach taken earlier by Thomason, in that the authors of [10] tackle the problem of identifying what one can say if one starts from certain natural, weaker assumptions that are, in a some sense, more in line with [9].

Theorem A′ is proved in Section 5 by means of a probabilistic construction. The basic underlying idea for the construction proving Theorem B′, which is similar in nature, was proposed by Łuczak [34].

1.3. Positive results for the sparse case. Given the importance of Theorems A and B, it is desirable to seek generalizations of these results to the ‘sparse’ case. Because of examples such as the ones we saw in Section 1.2, such generalizations will necessarily be somewhat complex; the straightforward generalizations simply fail to be true. In this section, we present two results that allows one to circumvent the difficulties illustrated by the examples in Section 1.2. More precisely, we shall discuss two results that state that the natural generalizations are true if we restrict ourselves to graphs that arise as subgraphs of random graphs. We do not discuss the proofs of these results in this section; we shall see later in this paper that a key idea in proving such results is to show that the number of counterexamples such as the ones given in Section 1.2 are extremely rare (for a more detailed discussion on this point, see Section 2).

As we shall see later when we discuss their applications in Section 1.4, the results that we present here are well-suited for approaching the issues discussed in Section 1.1 in the context of subgraphs of random graphs.

We now state our first main result, which may be thought of as a ‘pair condition for regularity’ (PCR); roughly speaking, this result shows that the implication “P_{2} ⇒ P_{1}” is valid in the context of subgraphs of random graphs. As usual, we write G(n, p) for the standard binomial random graph on n vertices and edge probability p. Theorem A′′ (Pair condition lemma, sparse setting). For any 0 < α ≤ 1, 0 < γ ≤ 1, and 0 < η ≤ 1, there exists a constant ε > 0 for which the following holds. Let ω = ω(n) be a function with ω → ∞ as n → ∞ and let 0 < p = p(n) < 1 and m_{0} = m_{0}(n) be such that

p^{2}m_{0} ≥ (log n)^{4}ω.  (5)

Then, with probability tending to 1 as n → ∞, we have that G = G(n, p) satisfies the following property. Suppose B is any bipartite subgraph of G, with vertex classes, say, U and W, with |U|, |W | ≥ m_{0}, and

T ≥ αp|U||W |  (6)

edges. Suppose further that B is (ε, T)-regular. Then, for all but ≤ η\binom{|U|}{2} pairs u_{1}, u_{2} ∈ U (u_{1} ≠ u_{2}), we have

| deg(u_{1}, u_{2}) − d^{2}|W || ≤ γd^{2}|W |,  (7)

where d = T/|U||W | is the density of B.

To have a complete analogue of Theorem A, the equivalence lemma, in the context of subgraphs of random graphs, we need a ‘local condition for regularity’ (LCR), that is, a result of the form “P_{1} ⇒ P_{2}” for this setting. We do prove such a result later in this paper, but, owing to its technical nature, we prefer to state it after we have developed some notation (see Lemma 15 and Theorem 16 in Section 4.2). Thus, we may claim that, at least in the context of sparse graphs that arise as subgraphs of random graphs, there is a full, natural generalization of the equivalence lemma, Theorem A. Most of this paper is devoted to justifying this claim.

Let us turn to an embedding lemma in the context of subgraphs of random graphs. Let us introduce a piece of notation. Let a real number 0 < ε ≤ 1 and integers T ≥ 1, k ≥ 1, and m be given. We say that a graph F is an (ε, T, k +1, m)- graph if it satisfies the following conditions:

(i) F is (k + 1)-partite, with all its vertex classes of cardinality m, (ii) all the \binom{k+1}{2} naturally induced m by m bipartite subgraphs of F have T

edges and are (ε, T)-regular.

We now give an embedding lemma for the complete graph K^{k+1} of order k + 1. Theorem B′′ (Embedding lemma, sparse setting). There is an absolute constant C > 0 for which the following holds. Let k ≥ 1 and 0 < α < 1 be given. Then there exist ε > 0 and B > 0 for which the following holds. Let

p = Bn^{−1/k}(log n)^{C}.  (8)

Then, with probability tending to 1 as n → ∞, we have that if F is an (ε, T, k+1, m)- graph, where

T ≥ αpm^{2}, m ≥ \frac{n}{log n}, and F ⊂ G = G(n, p),  (9)

where F is not necessarily an induced subgraph of G, then K^{k+1} ⊂ F. Theorem B′′ will be proved in a sequel to this paper.

1.3.1. A generalization of Theorem A′′. It turns out that a natural generalization of Theorem A′′, the pair condition lemma in the sparse setting, is useful in certain applications. Instead of considering pairs of vertices in a sparse regular pair, we may consider k-tuples of vertices, for some fixed k. The question is, then, whether most such k-tuples behave as though we were dealing with a genuine random bipartite graphs, namely, whether most such k-tuples are such that their joint neighbourhood has the expected cardinality. We address this question in this paper, and show that Theorem A′′ does indeed generalize to arbitrary fixed k (see Theorem 25). As we shall see in Section 1.4, such a generalization is useful in certain graph embedding problems.

1.3.2. The hereditary nature of ε-regularity. A fact that will play a crucial rôle in the proof of the generalization of Theorem A′′ discussed above is that the property of being ε-regular has a strong hereditary nature. Indeed, Section 4.3 will be entirely devoted to proving a family of results that illustrate this feature of ε-regularity (we refer to these results as the one-sided neighbourhood lemmas). Owing to their technical nature, we do not discuss these results here.

In a sequel to this paper [31], we shall consider two-sided neighbourhood lemmas; these lemmas will be important in the proof of Theorem B′′. For completeness, we state a two-sided neighbourhood lemma in Section 4.3.4.

1.4. Applications. Here, we discuss some applications of the results discussed so far. In all of the proofs of the applications that we mention below, the regularity lemma for sparse graphs, given in Section 3.2 below, Theorem 7, is used as the initial tool. The results discussed in Section 1.3 are then used to investigate the regular pairs that we obtain from this application of Theorem 7.

The results discussed in this section are proved elsewhere. In this paper, we concentrate on proving some of the basic lemmas discussed in Section 1.3.

1.4.1. Random graphs and fault-tolerance. Theorem 25 (see Section 1.3.1) is one of the tools used in the proof of a recent result concerning fault-tolerance properties of random graphs, proved by Alon, Capalbo, Ruciński, Szemerédi, and the authors [1]. In this section, we state and briefly discuss this result.

We need some definitions and notation. Let a real number 0 < η ≤ 1 be fixed, and suppose G and H are graphs. We write G →_{η} H if any subgraph J ⊂ G of G with size e(J) = |E(J)| ≥ ηe(G) contains an isomorphic copy of H as a subgraph. We extend this notation in the following way. Suppose that H is some family of graphs. We write

G →_{η} H  (10)

if any subgraph J ⊂ G of G with size e(J) = |E(J)| ≥ ηe(G) contains an isomorphic copy of every member H of H. In fact, we say that a graph G is η-fault-tolerant with respect to a family of graphs H if (10) holds.

In what follows, we shall be particularly interested in the family B(Δ; m, m) of m by m bipartite graphs with maximum degree Δ. In fact, a result in [1] implies that there are fairly small graphs that are η-fault-tolerant with respect to B(Δ; m, m) for any fixed η > 0. Indeed, there exist such graphs with n vertices and

≤ C_{1}n^{2−1/2Δ}(log n)^{1/2Δ}  (11)

edges, where n ≤ C_{2}m, and C_{1} = C_{1}(η, Δ) and C_{2} = C_{2}(η, Δ) are constants that depend only on Δ and η. On the other hand, the following result follows from a simple counting argument (see [1]): any graph G_{0} that is universal for the family B(Δ; m, m), that is, any graph G_{0} that contains isomorphic copies of all members of B(Δ; m, m), must satisfy

e(G_{0}) ≥ C_{3}m^{2−2/Δ}  (12)

for some absolute constant C_{3} > 0. Note that the bound in (12) does not require the graph G_{0} to be fault-tolerant. In view of (12), we may argue that the bound in (11) is quite satisfactory. Let us turn to the result in [1] that implies the bound in (11).

Let G(n, n; p) be the binomial bipartite random graph with both vertex classes of cardinality n and with edge probability p. The following result is proved in [1].

Theorem 2. For any 0 < η ≤ 1 and any Δ ≥ 2, there is a constant C = C(η, Δ) > 0 for which the following holds. Suppose

p = C (\frac{log n}{n})^{1/2Δ} and  m = ⌊n/C⌋.  (13)

Then, with probability tending 1 as n → ∞, the bipartite random graph G(n, n; p) satisfies

G(n, n; p) →_{η} B(Δ; m, m).  (14)

Besides making use of Theorem 25, the proof of Theorem 2 uses a hypergraph packing result due to Rödl, Ruciński, and Taraz [37].

1.4.2. Extremal problems for subgraphs of random graphs. The interplay between Ramsey theory and the theory of random graphs, beginning with the seminal work of Erdős [12], has deeply influenced both subjects. More recently, several authors investigated threshold functions for Ramsey properties (see, among others, [16, 18, 27, 35, 38, 39, 40, 44, 45]). The investigation of threshold functions for Turán type extremal problems is also under way [23, 24, 30], although a great deal more remains to be done in this direction. The fault-tolerance properties of random graphs discussed in Section 1.4.1 may be thought of as the degenerate case of the Turán type extremal problems we discuss now in this Section. (The readers interested in extremal and Ramsey properties of random graphs are referred to [25, Chapter 8].) In this section, we discuss the rôle of the results in Section 1.3 in this context.

It is not difficult to see that Theorem B′′, the embedding lemma in the sparse setting, implies the following result.

Theorem 3. There is an absolute constant C > 0 for which the following holds. Let k ≥ 1 and η > 0 be given. Then there exist B > 0 such that if

p = Bn^{−1/k}(log n)^{C},  (15)

then the random graph G(n, p) satisfies the relation

G(n, p) →_{1−1/k+η} K^{k+1}  (16)

with probability tending to 1 as n → ∞.

We now state a conjecture due to Łuczak and the authors [30] (see also [25, Chapter 8]) that says that, in fact, a great deal more than Theorem B′′ should be true.

As before, let H = H^{h} be a graph of order h ≥ 3 and suppose that H has vertices v_{1}, …, v_{h}. We define the 2-density of H to be

d_{2}(H) = max \{\frac{e(J) − 1}{|V (J)| − 2} : J ⊂ H, |V (J)| ≥ 3\} .  (17)

Let V = (V_{i})_{i=1}^{h} be h pairwise disjoint sets, all of cardinality m. We say that a graph F is an (ε, T, H; V)-graph if it satisfies the following conditions:

(i) F has vertex set ⋃_{1≤i≤h} V_{i}, (ii) for every edge {v_{i}, v_{j}} ∈ E(H) of H, the bipartite graph naturally induced

by V_{i} and V_{j} in F has T edges and is (ε, T)-regular. Let

F(ε, T, H; V) = {F: F is an (ε, T, H; V)-graph with H ⊄ F }.  (18)

If true, a far reaching generalization of Theorem B′′ would then be the following.

Conjecture 4. For any β > 0, there exist constants ε > 0 and C > 0 such that if

T ≥ Cm^{2−1/d_{2}(H)},  (19)

then, for all large enough m, we have

|F(ε, T, H; V)| ≤ β^{e(H)T} \binom{m^{2}}{T}^{e(H)}.  (20)

If H above is a forest, Conjecture 4 holds trivially, since, in this case, the family in (20) is empty for all large enough m. A lemma due to Łuczak and the authors [29] may be used to show that Conjecture 4 holds for the case in which H = K^{3}.

Some further remarks are in order. The fact that the validity of Conjecture 4 would imply embedding lemmas such as the one in Theorem B′′ comes from the considerations in Section 2. In fact, one would have embedding lemmas for general graphs H in dense and large enough o(1)-regular h-partite subgraphs of G(n, p) even if p is as small as

p = Cn^{−1/d_{2}(H)};  (21)

we leave the details to the reader. Note that, for the case in which H = K^{k+1}, relation (21) gives p = Cn^{−2/(k+1)}, which is better than (15).

1.4.3. An application to Ramsey theory. Our aim in this section is to state a result in Ramsey theory whose proof depends heavily upon, among others, the results in Section 1.3. We need some definitions and notation.

Let an integer r ≥ 2 be fixed, and suppose G and H are graphs. We write G → (H)_{r} if G contains a monochromatic copy of H in any edge-colouring of G with r colours. In fact, for simplicity, we restrict ourselves to the case in which we have only 2 colours, since for purposes of this section there is not much difference between the r = 2 and r ≥ 3 cases.

Following Erdős, Faudree, Rousseau, and Schelp [14], we define the size-Ramsey number of a graph H to be

r_{e}(H) = min{e(G): G → (H)_{2}}.  (22)

In words, the size-Ramsey number of a graph H is the minimal number of edges that a graph G may have and still be ‘Ramsey for H’, that is, be such that G → (H)_{2}. For instance, r_{e}(K(1, n)) = 2n − 1, where K(1, n) denotes the star with n edges.

In [6], Beck answered a question of Erdős [13], proving that there exists an absolute constant C ≤ 900 such that r_{e}(P_{n}) < Cn, where P_{n} denotes the path on n vertices. Later, in [7], Beck pointed out that there are trees with size Ramsey number at least n^{2}/8, and asked whether r_{e}(H(n, Δ)) < C_{Δ}n holds for any nvertex graph H(n, Δ) with maximum degree Δ. Beck’s question was answered affirmatively when H(n, Δ) is a cycle [22] or a tree [19].

Recently, Rödl and Szemerédi [43] proved that the answer to Beck’s question is negative already for Δ = 3. In fact, they showed that there are positive constants c and α so that, for every positive integer n, there are n-vertex graphs H with maximum degree Δ(H) = 3 such that

r_{e}(H) ≥ cn(log n)^{α}.  (23)

Set r_{e}(n, Δ) = max r_{e}(H), where the maximum is taken over all graphs H with n vertices and maximum degree Δ. The results in Section 4 are some of the tools that are used in the proof of the following result, due to Szemerédi and the authors [32].

Theorem 5. For any integer Δ ≥ 2, there is a real number ε = ε(Δ) > 0 for which we have

r_{e}(n, Δ) ≤ n^{2−ε}.  (24)

1.5. The organization of this paper. Let us now discuss the organization of this paper. In Section 2, we present a basic idea that allows us to prove results concerning large but arbitrary subgraphs of random graphs. In a few words, this idea consists of obtaining strong upper estimates for the the number of counterexamples to the property we wish to prove for such subgraphs, and then argue that such counterexamples do not occur in our random graph (see Lemma 6). In Section 3, we introduce some crucial definitions, we state a regularity lemma for sparse graphs, and also prove a few technical results on random graphs that will be used later. We close this section with two tail inequalities.

In Section 4, we state and prove the main results of this paper. Section 4.1 is devoted to the statement and proof of our pair condition lemma in the sparse context; in other words, we prove the analogue of the implication “P_{2} ⇒ P_{1}” (PCR) for this context. This result, which appears as Theorem A′′ above, is presented in two versions; see Lemma 12 (counting version) and Theorem 13 (random graphs version). Section 4.2 is devoted to the statement and proof of our local condition lemma in the sparse context; in other words, we prove the analogue of the implication “P_{1} ⇒ P_{2}” (LCR) for this context. Section 4.3 is devoted to the statement and proof of the one-sided neighbourhood lemmas. These results are crucial in the proof of the result discussed in Section 1.3.1 (see Theorem 25).

In Section 5, we prove Theorem A′.

Remark 4. The main results of this paper come in pairs. Indeed, usually we prove a counting version of our result and then we deduce a random graphs version. Typically, most of the work goes into proving the counting versions; the random graphs versions are often straightforward corollaries. Nevertheless, we shall state the counting versions as ‘lemmas’ and the random graphs versions are ‘theorems’, since the random graphs versions tend to be somewhat less technical and the reader may find them easier to apply.

1.6. Remarks on notation. Let us make the following comments on our notation explicitly.

Remark 5. If ε > 0, we write a ∼_{ε} b if

1 − ε ≤ \frac{a}{b} ≤ 1 + ε.  (25)

Note that the relation ∼_{ε} is not symmetric. We also sometimes write a ≍ b if there exist absolute constants c and C > 0 for which we have

cb ≤ a ≤ Cb.  (26)

Sometimes we write an adorned variant of ≍, for example, a ≍_{ϑ} b, to mean that the constants c and C hidden in this ≍ notation may depend on this quantity ϑ.

Remark 6. Usually, we are concerned with graphs whose order (typically n) tends to infinity. In the case of bipartite graphs, we shall have both vertex classes of large cardinality (typically, the vertex classes have order m_{1} and m_{2}). Occasionally, we write a ∼ b to mean that a/b → 1 as the order of the graph in question (or both vertex classes of the bipartite graph in question) tends to infinity. Similarly, we write a ≪ b to mean that a/b → 0. We often omit the qualification ‘for large enough n’ or ‘for large enough m_{1} and m_{2}.’ This should not lead to confusion.

Remark 7. Several constants will appear in the lemmas that follow. Often, when invoking a lemma, say Lemma N, it may be important to record that a certain constant, say ε, with some particular value, is involved in the current application of Lemma N. In this case, we write ε(N) for this particular value of this constant. This fussy notation will guard us against the proliferation of constants with equal or similar names that will appear in what follows.

Remark 8. Our notation will basically follow [8]. Since we are interested in asymptotic results, we shall often omit the floor and ceiling signs ⌊ ⌋, ⌈ ⌉, when they are not important.

2. Excluding counterexamples

There is a common underlying idea in the proofs that we present in this paper. This idea may be stated in a few words as follows: suppose we wish to show that,

(*) for almost all G = G(n, p), property S holds for every large enough sub-

graph H of G, where S is some given ‘absolute’ property of graphs (that is, given H, we may check whether or not H has S looking at H alone, disregarding G). In applications, ‘large enough’ will mean that we have

m = |V (H)| ≥ m_{0} = m_{0}(n) and T = e(H) = |E(H)| ≥ αp\binom{m}{2},  (27)

where m_{0} = m_{0}(n) is a reasonably fast growing function of n (say, some small power of n) and α > 0 is a constant independent of n. Now, observe that statements of the form (*) involve a quantification over a very large set of graphs H. Indeed, because of (27), we have T = e(H) = Ω(pm^{2}) and hence we are dealing with a quantity that is more than exponential in Ω(pm^{2}). We point out that this is indeed a large number in our context since the probability that G = G(n, p) is the empty graph is already

(1 − p)^{\binom{n}{2}} ≥ exp\{−2pn^{2}\}

if, say, p ≤ 1/2.

Füredi [20] observed that, in order to handle this difficulty, one may proceed as follows. First, we consider the family B = B(S) of counterexamples to assertion S. Then, we show that B is an asymptotically small family (we make this precise later). Finally, one then simply shows that, almost surely, such rare graphs do not occur in G(n, p) as subgraphs. This idea has proved to be quite useful, see [23, 27, 28, 29, 30]. (For an alternative approach, see [24, 39, 40, 41, 42].)

It turns out that the easiest way to apply Füredi’s idea is to show that the size of the family of counterexamples B(S) grows ‘superexponentially more slowly’ than the size of the family of all graphs. Let us make the following definition.

Definition 9. Let B be a family of labelled graphs and suppose β > 0 is a constant. Write B(m, T) for the graphs in B that have m vertices and T edges. For the sake of definiteness, suppose all graphs in B(m, T) have vertex set [m] = {1, …, m}. We shall say that B is a β-thin family if there exists an integer M such that, for all 0 ≤ T ≤ \binom{m}{2},

if m ≥ M, then |B(m, T)| ≤ β^{T} \binom{\binom{m}{2}}{T}.  (28)

Remark 10. We shall often consider families B of (labelled) bipartite graphs and in such cases we shall have independent parameters m_{1} and m_{2} for the number of vertices in each of the vertex classes. Such a family will be said to be β-thin if, instead of (28), we have

if m_{1}, m_{2} ≥ M, then |B(m_{1}, m_{2}; T)| ≤ β^{T} \binom{m_{1}m_{2}}{T},  (29)

where B(m_{1}, m_{2}; T) is the set of graphs in B that have m_{i} vertices in vertex class i (i ∈ {1, 2}).

Lemma 6. Let functions 0 < p = p(n) < 1 and m_{0} = m_{0}(n) such that

pm_{0} ≫ log n  (30)

be given, and consider the binomial random graph G = G(n, p). Then, for any fixed constant α > 0, there is a constant β = β(α) > 0 such that the following assertion holds. Suppose B is a β-thin family. Then almost every G = G(n, p) has the property that no copy H of a member of B satisfying (27) occurs as a subgraph of G.

Proof. Let α > 0 be given. We set

β = β(α) = \frac{α}{e^{3}} ,  (31)

and claim that this choice of β will do in our lemma. The proof of this claim will be an easy application of the first moment method. Let us estimate the expectation 𝔼(X) of the number of copies X = X_{B} of members of B in G = G(n, p) that satisfy (27). For integers m and T, let X(m, T) be the number of copies of elements of B(m, T) in G. Then, assuming that m ≥ M, where M is as given in Definition 9, an application of (28) gives that

𝔼(X(m, T)) ≤ (n)_{m}|B(m, T)|p^{T} ≤ n^{m}β^{T} \binom{\binom{m}{2}}{T}p^{T} .  (32)

We now observe that (27) implies that T^{−1}p\binom{m}{2} ≤ 1/α. Moreover, (27) and (30) give that m ≥ m_{0} ≫ log n and that T ≥ αp\binom{m}{2} ≥ αpm(m_{0} − 1)/2 ≫ m log n. Therefore, using (31), we may conclude (32) with

𝔼(X(m, T)) ≤ n^{m} (β \frac{ep\binom{m}{2}}{T})^{T} ≤ n^{m} (\frac{eβ}{α} )^{T} ≤ e^{m log n−2T} ≤ e^{−T} .  (33)

We now sum (33) over all m and all T satisfying (27) to obtain that

𝔼(X) = ∑_{m≥m_{0}} ∑_{T ≥αp\binom{m}{2}} 𝔼(X(m, T)) = ∑_{m≥m_{0}} ∑_{T ≥αp\binom{m}{2}} e^{−T}

≤ ∑_{m≥m_{0}} 2e^{−αp\binom{m}{2}} ≤ 2 ∑_{m≥m_{0}} n^{−m} = o(1), (34)

as n → ∞. The lemma follows from (34) and Markov’s inequality. □

In what follows, we shall show that two families of graphs are β-thin: see Remark 20 just after Lemma 12 and Remark 26 just after Lemma 19.

3. Preliminary results

3.1. Preliminary definitions. 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)|.

If B is a bipartite graph with vertex classes U and W and edge set E we write B = (U, W; E). Moreover, if G is a graph and U, W ⊂ V (G) are disjoint sets of vertices, we write G[U, W] for the bipartite graph naturally induced by U and W.

3.2. A regularity lemma for sparse graphs. Our aim in this section is to state a variant of the celebrated regularity lemma of Szemerédi [46].

Let a graph H = H^{n} = (V, E) of order |V | = n be fixed. Suppose η > 0, C > 1, and 0 < p ≤ 1. We say that H is an (η, C)-bounded 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) ≤ Cp|U||W |. In what follows, for any two disjoint non-empty sets U, W ⊂ V, let

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

We refer to d_{H,p}(U, W) as the p-density of the pair (U, W) in H. When there is no danger of confusion, we drop H from the subscript and write d_{p}(U, W).

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)| ≤ ε.

Below, we shall sometimes use the expression ε-regular with respect to density p to mean that (U, W) is an (ε, p)-regular pair. If B = (U, W; E) is a bipartite graph and (U, W) is an (ε, B, p)-regular pair, we say that B is an (ε, p)-regular bipartite graph.

We say that a partition Q = (C_{i})_{0}^{k} of V = V (H) is (ε, k)-equitable if |C_{0}| ≤ εn, and |C_{1}| = ⋯ = |C_{k}|. Also, we say that C_{0} is 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 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 (η, C)-bounded graphs.

Theorem 7. For any given ε > 0, C > 1, and k_{0} ≥ 1, there exist constants η = η(ε, C, k_{0}) and K_{0} = K_{0}(ε, C, k_{0}) ≥ k_{0} such that any graph H that is (η, C)-bounded 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}. □

Theorem 7 was independently observed by the present authors, and in fact a simple modification of Szemerédi’s proof of his lemma gives this result. For applications of this variant of the regularity lemma, see [26].

3.3. Further notation and definitions. We shall need some further notation and definitions concerning bipartite graphs. Throughout this section, we suppose we have a bipartite graph B with bipartition (U, W) with |U| = m_{1}, |W | = m_{2}, and T = e(U, W) > 0. We let p = T/m_{1}m_{2}, and d_{1} = pm_{1} and d_{2} = pm_{2}. Note that the p-density d_{B,p}(U, W) of (U, W) in B is 1.

In what follows, we shall be concerned with pairs {x, y} of vertices whose neighbourhoods intersect in an unexpected manner. In fact, for convenience, we introduce the following notation:

F (U, W; γ) = F_{B}(U, W; γ) = \{\{x, y\} ∈ \binom{U}{2}: |d_{W} (x, y) − \frac{d_{2}^{2}}{m_{2}} | ≥ γ \frac{d_{2}^{2}}{m_{2}} \} , (36)

where d_{W} (x, y) = d_{W}^{B} (x, y) = |W ∩ Γ_{B}(x) ∩ Γ_{B}(y)| = |Γ_{B}(x) ∩ Γ_{B}(y)|. The reader has most likely already observed the following fact. Suppose the bipartite graph B is drawn uniformly at random from all the m_{1} × m_{2} bipartite graphs with T edges. Then the expected value of d_{W} (x, y) with x ≠ y ∈ U is d_{2}^{2}/m_{2}.

Definition 11 (PC(U, W; γ, η)). Let B = (U, W; E) be a bipartite graph. We say that B has property PC(U, W; γ, η) if

|F_{B}(U, W; γ)| ≤ η\binom{|U|}{2}.  (37)

The notation for the property PC(U, W; γ, η) comes from the fact that we are concerned with pairs of vertices, and hence we have a certain pair condition. For convenience, we put PC(U, W; γ) = PC(U, W; γ, γ). We shall also be interested in a property concerning the ‘ℓ_{1}-uniformity’ of the degrees of the vertices in our bipartite graphs.

Definition 12 (D(U, W; δ, ε)). Let B = (U, W; E) be a bipartite graph. We say that B has property D(U, W; δ, ε) if

|e(U′, W) − p|U′||W || ≤ δp|U′||W | for all U′ ⊂ U with |U′| ≥ ε|U|.  (38)

Our next property on bipartite graphs is a certain one-sided inequality concerning their edge distribution. In fact, we are interested in a certain edge concentration bound.

Definition 13 (ECB(U, W; C)). Let B = (U, W; E) be a bipartite graph. Put d = min{d_{1}, d_{2}} and m = max{m_{1}, m_{2}}. We say that B has property ECB(U, W; C) if the following holds: whenever U′ ⊂ U and W′ ⊂ W are such that |U′|, |W′| ≥ d/(log m)^{3}, we have

e(U′, W′) ≤ Cp|U′||W′|.  (39)

The final property for bipartite graphs that we consider in this section is a little more technical. This property concerns the number of certain ‘cherries’ (paths of length 2) in the bipartite graph in question. In fact, the idea is that such cherries should not, in general, ‘concentrate’ on any set of pairs of vertices too much (this is made quantitatively precise through a certain cherry upper bound).

Definition 14 (ChUB(U, W; δ, C)). Let B = (U, W; E) be a bipartite graph. We say that B has property ChUB(U, W; δ, C) if

∑_{\{x,y\}∈F} d_{W} (x, y) ≤ Cδp^{2}|U|^{2}|W | for all F ⊂ \binom{U}{2} with |F | ≤ δ\binom{|U|}{2}, (40)

where, as before, d_{W} (x, y) = |Γ_{B}(x) ∩ Γ_{B}(y)|.

3.4. Elementary lemmas on random graphs. In this paragraph, we state and prove two simple lemmas concerning binomial random graphs.

3.4.1. The statement of the lemmas. We state the two lemmas in this section. The proofs are given in Section 3.4.2.

Lemma 8 (Edge concentration bound for r.gs). Let δ > 0 be a fixed constant. Almost every random graph G = G(n, q) is such that the following property holds. Suppose m = m(n) is such that

qm ≫ log n.  (41)

Then, for any two disjoint sets of vertices U, W ⊂ V (G) with |U|, |W | ≥ m = m(n), we have

e(U, W) ∼_{δ} q|U||W |.  (42)

Lemma 9 (Cherry upper bound for r.gs). Let δ > 0 be a fixed constant. Almost every random graph G = G(n, q) is such that the following property holds. Suppose m = m(n) is such that

q^{2}m ≫ log n.  (43)

Then, for any two disjoint sets of vertices U, W ⊂ V (G) with |U|, |W | ≥ m = m(n), we have that for all

F ⊂ \binom{U}{2} with |F | ≤ δ\binom{|U|}{2}  (44)

we have

∑_{{x,y}∈F} d_{W} (x, y) ≤ 2δq^{2}|U|^{2}|W |,  (45)

where d_{W} (x, y) = |W ∩ Γ(x) ∩ Γ(y)|.

Remark 15. It may be worth noting that condition (41) may be thought of as meaning that the degree of a vertex into the sets U and W should be large (namely, superlogarithmic in n). On the other hand, condition (43) requires that the expected number of common neighbours in the sets U and W, of a fixed pair of vertices, should be superlogarithmic in n.

3.4.2. Proofs of the elementary lemmas. The proof of Lemma 8 is immediate from Chernoff’s bound.

Proof of Lemma 8. By a simple averaging argument, we see that it suffices to prove the assertion for sets U and W with |U| = |W | = m. The probability that (42) fails is clearly at most exp{−c_{δ}q|U||W |} = exp{−c_{δ}qm^{2}}, where c_{δ} > 0 is some constant that depends only on δ > 0. The expected number of pairs (U, W) violating (42) is then

≤ \binom{n}{m}^{2}e^{−c_{δ}qm^{2}} ≤ exp\{2m log n − c_{δ}qm^{2}\} = o(1),  (46)

because of (41), and our lemma follows from Markov’s inequality. □

The proof of Lemma 9 is a little more interesting.

Proof of Lemma 9. Let a set of pairs F as in (44) be given. It is clear that we may assume that |F | = δ\binom{|U|}{2}. Suppose that, however, inequality (45) fails. Let us first show that this implies the existence of a matching M ⊂ F on which too many cherries ‘concentrate.’

For convenience, let us think of F as a graph on U and consider the line graph L(F) of F. Clearly, the maximum degree Δ′(F) = Δ(L(F)) of L(F) is at most 2(Δ(F) − 1) < 2|U|. Apply the Hajnal–Szemerédi theorem [21] to L(F) to obtain a decomposition of F into Δ′(F) + 1 matchings all of size

∼ t = |F |/Δ′(F).  (47)

It will be important later that these matchings should be fairly large. Note that, since we are assuming that |F | = δ\binom{|U|}{2}, we have

t = \frac{|F |}{Δ′(F)} > \frac{|F |}{2|U|} ∼ \frac{δ}{4}|U|.  (48)

We now let

k_{0} = \frac{2}{Δ′(F) + 1}δq^{2}|U|^{2}|W |,  (49)

and observe that this is the right-hand side of (45) divided by Δ′(F) + 1, the number of matchings in our Hajnal–Szemerédi decomposition of F. Now, since we are assuming that (45) fails, there must be a matching M ⊂ F in this decomposition for which we have

∑_{{x,y}∈M} d_{W} (x, y) > k_{0}.  (50)

Let us now work on the right-hand side of (50). Since we are assuming that |F | = δ\binom{|U|}{2}, in view of (48) and (49), we have

k_{0} ∼ 4\frac{q^{2}|F |}{Δ′(F) + 1}|W | ∼ 4q^{2}t|W |.  (51)

Therefore, the conclusion is that if (45) fails, then there exists a matching M for which we have

|M| ≳ \frac{δ}{4}|U|  (52)

(recall (48) and that |M| ∼ t) and, moreover,

∑_{{x,y}∈M} d_{W} (x, y) ≳ 4q^{2}|W ||M|.  (53)

Our aim now is to show that such a pair (W, M) almost surely does not occur in G = G(n, q). To this end, observe that, since

X = ∑_{{x,y}∈M} d_{W} (x, y) ∼ Bi(|W ||M|, q^{2}),  (54)

we have

ℙ(X ≥ k_{0}) ≤ \binom{|W ||M|}{k_{0}}q^{2k_{0}} ≤ (\frac{e|W ||M|}{k_{0}}q^{2})^{k_{0}} ≤ (\frac{e}{3})^{k_{0}} .  (55)

Therefore, the expected number of pairs (W, M) as above is

≤ \binom{n}{|W |}n^{2|M|} (\frac{e}{3})^{3q^{2}|M||W |} ≤ n^{|W |+2|M|} (\frac{e}{3})^{3q^{2}|M||W |}

= e^{(|W |+2|M|) log n} (\frac{e}{3})^{3q^{2}|M||W |} . (56)

We now claim that the last term of (56) is O(n^{−ω}) for some ω → ∞ as n → ∞. To see this, consider the exponents in the last term of (56), and observe that

q^{2} ≫ (\frac{1}{|M|} + \frac{2}{|W |}) log n.  (57)

To verify inequality (57), we use (43), (52), and the fact that |U|, |W | ≥ m, to see that

|M|q^{2} ≳ \frac{δ}{4}|U|q^{2} ≥ \frac{δ}{4}mq^{2} ≫ log n,  (58)

and that

|W |q^{2} ≥ mq^{2} ≫ log n.  (59)

The proof is not quite finished, since we still have to consider all possible values for the cardinalities of W and M. However, summing over all possible choices for |W | and |M|, we still have that the expected number of such pairs (W, M) is o(1). The result follows from Markov’s inequality. □

3.5. Elementary tail inequalities. Let us state two simple technical lemmas that will be useful in Section 4.3.

Lemma 10 (The hypergeometric tail lemma). Let b, d, k, and m be positive integers and suppose we select a d-set N uniformly at random from a set U of cardinality m. Suppose also that we are given a fixed b-set B ⊂ U. Then, writing k = λbd/m, we have

ℙ(|N ∩ B| ≥ k) = ∑_{j≥k} \binom{b}{j}\binom{m − b}{d − j}\binom{m}{d}^{−1} ≤ \binom{d}{k} (\frac{b}{m})^{k} ≤ (\frac{e}{λ})^{k} .  (60)

Proof. Without loss of generality, we suppose that U = [m] = {1, …, m} and B = [b]. Let us estimate the number of sets N for which |N ∩ B| ≥ k in the following way. First choose the smallest k elements of such a set N. Note that these elements must all be in B. Thus there are \binom{b}{k} ways of making this choice. Now choose the remaining d − k elements of N; there are at most \binom{m−k}{d−k} ways of doing this. Therefore, we have that

ℙ(|N ∩ B| ≥ k) ≤ \binom{b}{k}\binom{m − k}{d − k}\binom{m}{d}^{−1} = \binom{d}{k}\frac{(b)_{k}(m − k)_{d−k}}{(m)_{d}} .  (61)

Now observe that (m)_{d} = (m)_{k}(m − k)_{d−k}, and hence the right-hand side of (61) is in fact

\binom{d}{k}\frac{(b)_{k}}{(m)_{k}} ≤ \binom{d}{k} (\frac{b}{m})^{k} ≤ (\frac{edb}{km})^{k} .  (62)

Since k = λbd/m, relation (60) follows. □

Our second lemma concerns the number of edges that we typically capture when we select a random d-set of vertices of a sparse graph. Let us describe the set-up we are concerned with.

Let a graph F = (U, E) with |U| = m and |E| ≤ η\binom{m}{2} be given. Suppose we select a d-set N uniformly at random from U. We are then interested in giving an upper bound for e(F [N]), the number of edges that the set N will induce in F.

Lemma 11 (The two-day lemma). For every α, β > 0, there exist η_{0} = η_{0}(α, β) > 0 such that, whenever 0 < η ≤ η_{0}, we have

ℙ (e(F [N]) ≥ α\binom{d}{2}) ≤ β^{d}.  (63)

Remark 16. To avoid any possibility of confusion, we observe that an equivalent formulation of (63) is that

|\{N ∈ \binom{U}{d}: e(F [N]) ≥ α\binom{d}{2}\}| ≤ β^{d}\binom{m}{d}.  (64)

Proof of Lemma 11. We may assume that

d ≤ m/100,  (65)

say. Indeed, if d > m/100, it suffices to take η_{0} small enough so that

α\binom{d}{2} > η_{0}\binom{m}{2}.  (66)

If (66) holds, any d-set N will be such that e(F [N]) < α\binom{d}{2}. Thus we assume that (65) holds. Clearly, it suffices to prove the following variant of our lemma:

(†) for any 0 < γ ≤ 1/2, there is η_{0} = η_{0}(γ) such that, for any 0 < η ≤ η_{0}, we have

ℙ (e(F [N]) ≥ γ\binom{d}{2}) ≤ 2γ^{d}.  (67)

We proceed to prove (†). Let

c = \frac{γ}{100 exp\{200γ^{−1} log(1/γ)\}}  (68)

and let λ be such that

log λ = 200γ^{−1} log(1/γ).  (69)

Observe that then

λc = γ/100.  (70)

Finally, we let η_{0} = η_{0}(γ) be defined by

η_{0} = \frac{cγ^{1+10/γ}}{20 × 4^{10/γ}} .  (71)

We shall prove that this choice of η_{0} will do in (†). Thus, suppose that we have 0 < η ≤ η_{0}. We have to verify (67).

Let

B = {x ∈ U: d_{F} (x) ≥ (η/c)(m − 1)},  (72)

and observe that, then, we have

|B| ≤ cm,  (73)

since e(F) ≤ η\binom{m}{2}. By the hypergeometric tail lemma (Lemma 10), we see that

ℙ(|N ∩ B| ≥ λcd) ≤ (\frac{e}{λ})^{λcd} ≤ exp\{(1 − log λ)λcd\}

≤ exp \{−\frac{1}{2}(log λ)λcd\} = exp \{−d log \frac{1}{γ} \} = γ^{d}, (74)

where in the last inequality we used (69) and (70). We shall now consider the case in which

|N ∩ B| < λcd = \frac{1}{100}γd.  (75)

Let us generate the vertices u_{1}, …, u_{d} of N sequentially, in this order, at random. Let us assume that (75) holds; notice that there are at most 2^{d} choices for the set I of indices 1 ≤ i ≤ d for which u_{i} ∈ B. Let x_{1}, …, x_{d′} be the vertices u_{i} with i ∉ I, where d′ = |N \ B| ≥ (1 − γ/100)d, and we think of them being chosen in this order. In what follows, we shall argue that the choice of many of these vertices x_{i} is rather constrained, and we shall thus derive a strong bound for the probability of the event

\{N: |N ∩ B| < λcd\} ∩ \{N: e(F [N]) ≥ γ\binom{d}{2}\}  (76)

Now, from (75), it follows that the number of edges in F [N] that touch vertices in B is at most γd^{2}/100. If we induce ≥ γ\binom{d}{2} edges in N, we must have

≥ γ\binom{d}{2} − \frac{1}{100}γd^{2} ≥ \frac{1}{2}γ\binom{d}{2}  (77)

edges within F [N \ B] = F [x_{1}, …, x_{d′}]. Suppose that we have already chosen x_{1}, …, x_{i−1}, and that we are about to choose x_{i}. Since all vertices x_{j} (j < i) are not in B, we have that the number of edges incident to {x_{j}: j < i} is less than (i − 1)(η/c)(m − 1). We have to choose x_{i} from

U_{i} = U \ (B ∪ {x_{j}: j < i}).  (78)

Because of (65), (68), and (73), we have that |U_{i}| ≥ m/2, with plenty to spare. Hence the average degree into {x_{j}: j < i} of a vertex in U_{i} is

≤ (i − 1)\frac{η}{c} (m − 1)/ |U_{i}| ≤ \frac{iη}{c} m /\frac{m}{2} = \frac{2iη}{c} .  (79)

Since we are supposed to get ≥ (γ/2)\binom{d}{2} edges within N \ B = \{x_{i}: 1 ≤ i ≤ d′\} (cf. (77)), we must have at least γd/10 indices i for which we have

|Γ(x_{i}) ∩ \{x_{j}: j < i\}| ≥ \frac{γ}{10}i.  (80)

Indeed, otherwise the number of edges in F [N \ B] would be at most

\frac{γd}{10} × d + d × \frac{γd}{10} < \frac{γ}{2} \binom{d}{2},

which would contradict the bound in (77). Now, the bound on the average degree (79) and Markov’s inequality tells us that the probability that (80) happens for a given index i is

≤ \frac{2iη/c}{iγ/10} = \frac{20η}{cγ} .

Let us observe again that there are at most 2^{d} choices for the set I of indices 1 ≤ i ≤ d for which u_{i} ∈ B. Moreover, there are at most 2^{d} choices for the set, say J, of indices 1 ≤ i ≤ d for which the choice of x_{i} results in a vertex for which (80) holds.

Putting all of the above together, we see that the probability that the event in (76) happens is

≤ 2^{d} × 2^{d} × (\frac{20η}{cγ} )^{γd/10} = (\frac{20 × 4^{10/γ}}{cγ} η)^{γd/10} .  (81)

In (81), one of the 2^{d} accounts for the number of choices for I and the other for the number of choices for J. Observe that the right-hand side of (81) is at most γ^{d}, because η ≤ η_{0} and η_{0} is as given in (71). We conclude that the probability of the event in (76) is at most γ^{d}. Combining this with (74), we see that (†) does hold. □

4. Regular pairs in sparse random graphs

The main results of this paper are given in this section. Section 4.1 is devoted to the statement and proof of our pair condition lemma in the sparse context; see Theorem A′′ in Section 1.3 and Lemma 12 and Theorem 13 in Section 4.1. Section 4.2 is devoted to the statement and proof of our local condition lemma in the sparse context; see the discussion just after Theorem A′′ in Section 1.3. Section 4.3 is devoted to the statement and proof of the one-sided neighbourhood lemmas; see the short discussion in Section 1.3.2 concerning these results.

Finally, in Section 4.4, we state and prove the generalization of Theorem A′′ briefly discussed in Section 1.3.1.

4.1. The pair condition lemma. We state and prove here a counting lemma (Lemma 12) concerning sparse ε-regular bipartite graphs that fail to satisfy a certain local ‘pseudorandomness’ condition. In fact, we are interested in showing that the overwhelming majority of ε-regular bipartite graphs B = (U, W; E) are such that property PC(U, W; γ) holds, as long as ε ≤ ε_{0}(γ). Our estimates will be strong enough to imply that a.e. random graph G = G(n, p) has the following property: any large and dense enough bipartite subgraph B = (U, W; E) of G that is ε-regular does in fact satisfy PC(U, W; γ), as long as ε ≤ ε_{0}(γ) (cf. Theorem 13).

Remark 17. In the dense case, the o(1)-regularity of a bipartite graph B = (U, W; E) implies property PC(U, W; o(1)). Unfortunately, this may fail if p = p_{B}(U, W) = e(B)/|U||W | → 0 as n → ∞ (see Section 5). The results below, Lemma 12 and Theorem 13, are alternative tools for handling the sparse case.

Remark 18. The proof of Lemma 12 is similar in many aspects to the proof of Lemma 7 in Section 2.1 of [30].

4.1.1. The statement of the lemma. We start by describing the set-up of interest. We are concerned with bipartite graphs B = (U, W; E) for which the following conditions and notation apply:

(i) (a) |U| = m_{1}, |W | = m_{2}, and B has e(B) = T edges. Let p = T/m_{1}m_{2} and d_{i} = pm_{i} (i ∈ {1, 2}). Set m = m_{+} = max{m_{1}, m_{2}} and m_{−} =

min{m_{1}, m_{2}}.

(b) For some function ω → ∞ as m_{1}, m_{2} → ∞, we have

T ≥ ωm_{−}^{1/2}m_{+}(log m_{+})(log m_{2})^{1/2}.  (82)

(ii) B is ε-regular with respect to density p.

(iii) B has property ECB(U, W; C).

(iv) B fails to have property PC(U, W; γ). Given U, W, ω, ε, γ, and C as above, we let

B(U, W, ω; ε, γ, C) = {B = (U, W; E): (i)–(iv) above hold}.  (83)

In other words, B = B(U, W, ω; ε, γ, C) is the family of bipartite graphs B = (U, W; E) that satisfy (i)–(iv) above; note that the number of edges T of B is arbitrary, except that of course we require that (82) should hold. If T is a given integer, we let

B(U, W, ω; ε, γ, C; T) = {B ∈ B(U, W, ω; ε, γ, C): B has T edges}.  (84)

Lemma 12 (The pair condition lemma, counting version). For all β > 0, γ > 0, C ≥ 1, and ω = ω(m_{1}, m_{2}) such that ω(m_{1}, m_{2}) → ∞ as m_{1}, m_{2} → ∞, there exists an ε > 0 such that, for any 0 ≤ T ≤ m_{1}m_{2}, we have

|B(U, W, ω; ε, γ, C; T)| ≤ β^{T} \binom{m_{1}m_{2}}{T}.  (85)

Remark 19. Let us observe that the condition on T in (i)(b) is equivalent to

p^{2}m_{−} ≥ ω^{2}(log m_{+})^{2} log m_{2}.  (86)

Roughly speaking, inequality (86) says that the expected size of the joint neighbourhood of two vertices in the same vertex class in B should be of reasonable size.

Remark 20. In the language of Section 2 (see Definition 9 and Remark 10), Lemma 12 tells us that

B(U, W, ω; ε, γ, C)  (87)

is a β-thin family as long as ε is suitably small. It will be important in applications that we may choose β, γ, and C as we please, and we still have a ‘good’ choice for ε to make the family in (87) a β-thin family.

Finally, we observe that calculations analogous to the ones in the proof of Lemma 6 will show that, roughly speaking, random graphs almost surely do not contain ‘large’ subgraphs isomorphic to the members of the family in (87) (cf. Theorem 13).

We now state the result concerning random graphs that may be deduced from Lemma 12.

Theorem 13 (The pair condition lemma, r.gs version). Suppose 0 < q = q(n) < 1 and m_{0} = m_{0}(n) are such that

q^{2}m_{0} ≫ (log n)^{4}.  (88)

Then, for all α > 0 and γ > 0, there is ε > 0 for which the following assertion holds. Almost every G = G(n, q) is such that any (ε, q)-regular bipartite subgraph B = (U, W; E) ⊂ G of it, with |U|, |W | ≥ m_{0} and |E| ≥ αe(G[U, W]), satisfies property PC(U, W; γ).

4.1.2. Proof of the pair condition lemma. We prove Lemma 12 in this section.

To distinguish between the two rôles played by γ in property PC(U, W; γ) in condition (iv), we consider the condition

(iv′) B fails to have property PC(U, W; γ, η).

Clearly, to prove Lemma 12, it suffices to show the following assertion:

(*) for all β > 0, γ > 0, η > 0, and C ≥ 1, there exists an ε > 0 such that the

number of graphs satisfying (i)–(iii) and (iv′) satisfies (85). In fact, we shall show that (*) follows from a claim we state below (see Claim 14).

The proof of this claim will be, however, somewhat lengthy. Let us now give an outline of the proof of (*), since this should help motivate the statement of Claim 14.

Sketch of the proof of (*). Let B be the set of all graphs satisfying (i)–(iii) and (iv′), where U and W are fixed. Let now B ∈ B be fixed. Since PC(U, W; γ, η) does not hold, i.e., inequality (37) fails, there is a partition U = U_{1} ∪ U_{2} of U with ≳ ηm_{1}^{2}/4 elements of F_{B}(U, W; γ) ‘going across’ the U_{1}–U_{2} partition. Moreover, we may assume that |U_{1}| = ⌊m_{1}/2⌋. Let us fix such a partition of U and let us consider the bipartite graph F_{γ} = (U_{1}, U_{2}; F) naturally induced by F_{B}(U, W; γ). Now put

S = S(B) = \{u ∈ U_{2} : d^{F_{γ}} (u) ≥ \frac{η}{5} m_{1}\} ,  (89)

where d^{F_{γ}} (u) denotes the degree of u in the bipartite graph F_{γ}. Note that

|S| ≥ \frac{η}{5} m_{1}.  (90)

Indeed, otherwise we would have

e(F_{γ}) ≤ \frac{η}{5} m_{1} × ⌈\frac{m_{1}}{2} ⌉ + ⌊\frac{m_{1}}{2} ⌋ × \frac{η}{5} m_{1} < \frac{1}{4}ηm_{1}^{2},  (91)

which would be a contradiction to the choice of the partition U = U_{1}∪U_{2}. Let B_{1} = (U_{1}, W; E_{1}) be the subgraph of B induced by (U_{1}, W) and note that then, because of the (ε, p)-regularity of B (see (ii)), we have

T_{1} = e(B_{1}) ∼_{ε} \frac{T}{2} .

We have shown that to any B ∈ B we may associate a pair Λ = Λ(B) = (B_{1}, S) with B_{1} and S as above. Fix one such Λ(B) for each B ∈ B in an arbitrary fashion, and consider the naturally induced partition

B = ⋃_{Λ} B_{Λ}.  (92)

To prove that |B| is bounded by (85), we shall estimate each |B_{Λ}| separately and then we shall sum over all possible pairs Λ = (B_{1}, S). We leave the details for later. □

Claim 14 will be used to estimate |B_{Λ}|, where the notation is as (92). Before we proceed, we need to introduce the set-up that interests us in this claim.

Throughout this section, we keep the notation as defined in conditions (i)–(iii) given before the statement of Lemma 12. We shall now be interested in bipartite graphs B_{1} = (U_{1}, W; E_{1}), where U_{1} ⊂ U, and sets N ⊂ W with |N| ∼_{ε} d_{2} for which the following conditions, definitions, and notation apply:

(i) |U_{1}| = ⌊m_{1}/2⌋ and e(B_{1}) = T_{1} ∼_{ε} T/2. Moreover, N ⊂ W is a subset of W of cardinality |N| = d′_{2} ∼_{ε} d_{2}.

(ii) For all U′ ⊂ U_{1} and W′ ⊂ W with |U′| ≥ εm_{1} and |W′| ≥ εm_{2}, we have

|d_{B_{1},p}(U′, W′) − 1| ≤ ε,  (93)

where p = T/|U||W |. Recall that d_{B_{1},p}(U′, W′) = e_{B_{1}}(U′, W′)/p|U′||W′| is the p-density of the pair (U′, W′) in B_{1} (cf. Section 3.2).

(iii) For all U′ ⊂ U_{1} and W′ ⊂ W with |U′| and |W′| ≥ d/(log m)^{3}, we have

e_{B_{1}}(U′, W′) ≤ Cp|U′||W′|.  (94)

Here, d = min{d_{1}, d_{2}} and m = m_{+} = max{m_{1}, m_{2}}. Note that d = T/m. (iv) (a) Consider

D = \{y ∈ U_{1} : ||Γ(y) ∩ N| − \frac{d′_{2}d_{2}}{m_{2}} | > γ \frac{d′_{2}d_{2}}{m_{2}} \} ,  (95)

and observe that D is the set of vertices y ∈ U_{1} whose neighbourhood sets Γ(y) ⊂ W do not intersect N in the expected way (recall that |N| = d′_{2}; see (i) above). Indeed, y ∈ D if and only if |Γ(y) ∩ N| presents a significant deviation from the ‘expectation’ d′_{2}d_{2}/m_{2}. Moreover, consider the partition D = D^{−} ∪D^{+} with y ∈ D^{−} if |Γ(y)∩N| < (1 − γ)d′_{2}d_{2}/m_{2} and y ∈ D^{+} if |Γ(y) ∩ N| > (1 + γ)d′_{2}d_{2}/m_{2}.

(b) |D| ≥ (η/5)m_{1}.

Remark 21. Intuitively, we may think of N above as the neighbourhood set of a vertex x in U_{2} in some graph B ∈ B_{Λ} with Λ = (B_{1}, S) and x ∈ S.

We are now ready to state our claim.

Claim 14. For all β_{1} > 0, η > 0, γ > 0, and C ≥ 1, there is ε > 0 such that, for any fixed graph B_{1} as above, the number of d′_{2}-sets N for which (i)–(iv) are satisfied is

≤ β_{1}^{d′_{2}} \binom{m_{2}}{d′_{2}}.  (96)

Before we prove Claim 14, we deduce (*) assuming this claim.

Proof of (*). Let β, γ, η, and C as in (*) be given. Let us define positive constants β_{1}, β_{2}, and β_{3} by setting

β_{3} = β^{2},  β_{2} = β_{3}^{2}, and β_{1} = β_{2}^{10/η}.  (97)

We wish to apply Claim 14. Let β_{1}(14) = β_{1} (here we are using the convention in Remark 7). We now let

η(14) = η,  γ(14) = γ, and C(14) = C.  (98)

Claim 14 applied to constants β_{1}(14), η(14), γ(14), and C(14) gives us a constant ε(14) > 0. We now let

ε = min \{ε(14), \frac{1}{60}η\} .  (99)

We claim that this choice of ε will do in (*), and proceed to prove this claim.

Let us consider the decomposition B = ⋃ B_{Λ} given in (92). Fix Λ = (B_{1}, S). For each B ∈ B_{Λ}, we have a naturally associated bipartite graph B_{2} = (U_{2}, W; E_{2}) such that B = B_{1}∪B_{2}. Let T_{2} = e(B_{2}) = T −T_{1}. Moreover, put m′_{1} = ⌊m_{1}/2⌋ and m′′_{1} = ⌈m_{1}/2⌉. Suppose U_{2} = {u_{1}, …, u_{m′′_{1}}}, and consider the degree sequence d = d(B_{2}) = (f_{i})_{1≤i≤m′′_{1}}, where f_{i} = d_{B_{2}}(u_{i}) holds for all 1 ≤ i ≤ m′′_{1}. Since B ∈ B_{Λ} ⊂ B is (ε, p)-regular, we know that f_{i} ∼_{ε} d_{2} for all but ≤ 2εm_{1} indices 1 ≤ i ≤ m′′_{1}.

Let

S′ = {u ∈ S: d_{B_{2}}(u) ∼_{ε} d_{2}}.  (100)

Since ε ≤ η/60 (see (99)), we have, from (90), that

|S′| ≥ (\frac{η}{5} − 2ε) m_{1} ≥ \frac{η}{6} m_{1}.  (101)

Let

B_{Λ} = ⋃_{d} B_{Λ,d}  (102)

be the partition of B_{Λ} induced by the degree sequences d = d(B_{2}) = (f_{i})_{1≤i≤m′′_{1}}.

Let us write ∑_{i}^{S′} for the sum over all 1 ≤ i ≤ m′′_{1} such that u_{i} ∈ S′. We then have, by Claim 14,

|B_{Λ,d}| ≤ ∏ \{β_{1}^{f_{i}} \binom{m_{2}}{f_{i}}: u_{i} ∈ S′\} ∏ \{\binom{m_{2}}{f_{i}}: u_{i} ∉ S′\}

= ∏_{1≤i≤m′′_{1}} \binom{m_{2}}{f_{i}} ∏ \{β_{1}^{f_{i}}: u_{i} ∈ S′\} ≤ \binom{m′′_{1}m_{2}}{T_{2}}β_{1}^{∑_{i}^{S′} f_{i}}. (103)

From (100) and (101), we have

∑_{i}^{S′} f_{i} ≥ (1 − ε)d_{2}|S′| ≥ (1 − ε)\frac{η}{6} m_{1}d_{2} ≥ \frac{η}{10}T,

where in the last inequality we used that ε ≤ η/60 ≤ 1/60 < 2/5. Therefore, by (97), the right-hand side of (103) is

≤ \binom{m′′_{1}m_{2}}{T_{2}}β_{2}^{T} .  (104)

We now wish to sum (104) over all possible d = (f_{i})_{1≤i≤m′′_{1}} to obtain an estimate for |B_{Λ}|. To estimate this sum, we use that

(T_{2} + 1)^{m′′_{1}−1}β_{2}^{T/2} ≤ (T + 1)^{m_{1}}β_{2}^{T/2} ≤ 1,  (105)

which follows from (82), since that lower bound for T implies that T ≥ ωm_{+} log m_{+} ≥ ωm_{1} log m_{1}. We thus estimate |B_{Λ}| as follows, making use of (102)–(105) and (97):

|B_{Λ}| = ∑_{d} |B_{Λ,d}| ≤ \binom{T_{2} + m′′_{1} − 1}{m′′_{1} − 1}\binom{m′′_{1}m_{2}}{T_{2}}β_{2}^{T}

≤ (T_{2} + 1)^{m′′_{1}−1}\binom{m′′_{1}m_{2}}{T_{2}}β_{2}^{T} ≤ (T + 1)^{m_{1}} \binom{m′′_{1}m_{2}}{T_{2}}β_{2}^{T}

≤ \binom{m′′_{1}m_{2}}{T_{2}}β_{2}^{T/2} = \binom{m′′_{1}m_{2}}{T_{2}}β_{3}^{T} . (106)

Observe that, again by the lower bound on T in (82), we have

2^{m_{1}+m′′_{1}}β_{3}^{T/2} ≤ 1.  (107)

We now sum (106) over all possible Λ = (B_{1}, S) and use (107) to obtain

|B| = ∑_{T_{1}∼_{ε}T/2} ∑ {|B_{Λ}|: Λ such that e(B_{1}) = T_{1}}

≤ ∑_{T_{1}∼_{ε}T/2} 2^{m_{1}} \binom{m′_{1}m_{2}}{T_{1}}2^{m′′_{1}} \binom{m′′_{1}m_{2}}{T_{2}}β_{3}^{T} ≤ β_{3}^{T/2} ∑_{T_{1}} \binom{m′_{1}m_{2}}{T_{1}}\binom{m′′_{1}m_{2}}{T_{2}}

= β^{T} ∑_{T_{1}} \binom{m′_{1}m_{2}}{T_{1}}\binom{m′′_{1}m_{2}}{T_{2}} = β^{T} \binom{m_{1}m_{2}}{T}. (108)

Inequality (108) completes the proof of (85), assuming Claim 14. □

To complete the proof of Lemma 12, it remains to prove Claim 14.

Proof of Claim 14. Let constants β_{1}, η, γ, and C as in the statement of the claim be given. Let ε_{0} > 0 be such that

2 (\frac{6eCε_{0}}{γ} )^{γ/3C} ≤ \frac{1}{2}β_{1}.  (109)

We now put

ε = min \{\frac{1}{40}η, \frac{1}{6}γ, ε_{0}\} ,  (110)

and assert that this choice for ε will do in Claim 14. To verify this assertion, we count the N in question by considering two cases, according to the sizes of D^{+} and D^{−}.

We start with the case in which |D^{+}| is large.

Case 1. |D^{+}| ≥ (η/10)m_{1}

Our aim is to show that the number of sets N as in the statement of the claim that fall in this case is

≤ \frac{1}{2}β_{1}^{d′_{2}} \binom{m_{2}}{d′_{2}}.  (111)

We start by establishing the following assertion.

(†) There is a set Y ⊂ D^{+} such that (i) d(y) ∼_{ε} d_{2} = pm_{2} for all y ∈ Y,

(ii) |Γ(w) ∩ Y | ∼_{2ε} p|Y | for at least (1 − 2ε)m_{2} vertices w ∈ W,

(iii) |Y | ∼ (η/20)(d/(log m)^{2}).

Proof of (†). Let U^{∗} ⊂ U_{1} be the set of vertices u in U_{1} that have degree d(u) satisfying |d(u) − d_{2}| > εd_{2}. Note that |U^{∗}| < 2εm_{1}, since (ii) holds. Clearly,

|D^{+} \ U^{∗}| ≥ (\frac{η}{10} − 2ε) m_{1} ≥ \frac{1}{20}ηm_{1},  (112)

since ε ≤ η/40 (cf. (110)). Fix an arbitrary subset D′ ⊂ D^{+} \ U^{∗} with

|D′| = \frac{1}{20}ηm_{1}.  (113)

We select for Y a random subset of D′ by putting every element of D′ in Y independently with probability

ℙ(y ∈ Y) = \frac{d}{m_{1}(log m)^{2}} .  (114)

Then we have

𝔼(|Y |) = \frac{η}{20}m_{1} × \frac{d}{m_{1}(log m)^{2}} = \frac{ηd}{20(log m)^{2}} .  (115)

For w ∈ W and X ⊂ U_{1}, put d_{X}(w) = |Γ(w) ∩ X|. Note that d_{D′}(w) ∼_{ε} p|D′| for at least (1 − 2ε)m_{2} vertices w ∈ W, because (ii) holds. For any such w, we have

𝔼(d_{Y} (w)) ∼_{ε} p\frac{η}{20}m_{1} × \frac{d}{m_{1}(log m)^{2}} = p 𝔼(|Y |).  (116)

Note that, because of (82) and (115), we have

p 𝔼(|Y |) = \frac{η}{20} × \frac{T}{m_{1}m_{2}} × \frac{T/m}{(log m)^{2}} ≫ log m_{2}.  (117)

Therefore, standard estimates for the binomial distribution tell us that a set Y as required exists. □

Remark 22. Note that we have found a set Y as in (†) given a set N as in the statement of Claim 14 that, furthermore, satisfies the hypothesis of Case 1. In particular, Y = Y (N) depends on N.

Remark 23. To estimate the number of sets N for which Case 1 applies, we shall estimate the number of such N with a given fixed Y = Y (N). To complete the estimation, it suffices to sum over all possible Y. Note that, because of (†)(iii) and (82), the number of such Y is

≤ \binom{m_{1}}{d/(log m)^{2}} ≤ (\frac{em_{1}}{d} (log m)^{2})^{d/(log m)^{2}} = (\frac{em_{1}m}{T}(log m)^{2})^{d/(log m)^{2}}

≤ (m_{1} log m)^{d/(log m)^{2}} ≤ exp{2d/ log m} ≤ (1 + o(1))^{d_{2}}, (118)

which is a negligible factor (cf. (111)).

We fix a set Y as in (†) and proceed with the proof of Case 1. Let W′ ⊂ W be the subset of W of the ‘exceptional’ vertices, namely,

W′ = {w ∈ W: |Γ(w) ∩ Y | ∼_{2ε} d̄_{Y} fails},  (119)

where

d̄_{Y} = p|Y | ∼ \frac{d_{1}}{m_{1}} × \frac{ηd}{20(log m)^{2}} = \frac{ηdd_{1}}{20m_{1}(log m)^{2}} .  (120)

Because of (†)(ii), we know that

|W′| ≤ 2εm_{2}.  (121)

Our aim now is to show that, because of the existence of the set Y, the set N has to intersect W′ in an unexpectedly substantial manner. Our simple inequality for the tail of the hypergeometric distribution, Lemma 10, will then finish the proof of this case.

Let us count the number of edges between Y and N. On the one hand, since Y ⊂ D^{+}, we have

e(N, Y) = ∑_{y∈Y} |Γ(y) ∩ N| ≥ (1 + γ) ∑_{y∈Y} \frac{d′_{2}d_{2}}{m_{2}} = (1 + γ)|Y |\frac{d′_{2}d_{2}}{m_{2}} .  (122)

Since (†)(iii) holds, we conclude that

e(N, Y) ≳ (1 + γ)\frac{ηdd′_{2}d_{2}}{20m_{2}(log m)^{2}} .  (123)

On the other hand, we have

e(N, Y) = ∑_{w∈N} |Γ(w) ∩ Y | = ∑_{w∈N\W′} |Γ(w) ∩ Y | + ∑_{w∈N∩W′} |Γ(w) ∩ Y |

≤ |N \ W′|(1 + 2ε)d̄_{Y} + e(N ∩ W′, Y)

≤ (1 + 2ε)d′_{2} \frac{ηdd_{1}}{20m_{1}(log m)^{2}} + e(N ∩ W′, Y). (124)

Comparing (123) and (124) and using that p = d_{1}/m_{1} = d_{2}/m_{2} and that ε ≤ γ/6 (cf. (110)), we obtain that

e(N ∩ W′, Y) ≥ \frac{γ}{2} × \frac{ηpdd′_{2}}{20(log m)^{2}} .  (125)

We now apply (iii). Put |N ∩ W′| = αd′_{2}. Suppose first that |N ∩ W′| = αd′_{2} < d/(log m)^{3}. Then, in fact, we extend the set N ∩ W′ to a larger set Z ⊂ W with |Z| = d/(log m)^{3} arbitrarily, so that we may indeed apply inequality (94) in (iii). We obtain that

e(N ∩ W′, Y) ≤ e(Z, Y) ≤ Cp|Z||Y | = Cp|Y | × \frac{d}{(log m)^{3}} .  (126)

However, we shall see that (126) leads to a contradiction. Indeed, comparing (125) and (126), and using (†)(iii), we obtain that

\frac{γ}{2} × \frac{ηpdd′_{2}}{20(log m)^{2}} ≤ e(N ∩ W′, Y)

≤ Cp|Y |\frac{d}{(log m)^{3}} ∼ Cp × \frac{ηd}{20(log m)^{2}} × \frac{d}{(log m)^{3}} , (127)

which implies that

\frac{1}{2}γd′_{2} ≲ \frac{Cd}{(log m)^{3}} .  (128)

However, inequality (128) cannot hold for large m, since d = min{d_{1}, d_{2}} and d′_{2} ∼_{ε} d_{2}. This contradiction shows that

|N ∩ W′| = αd′_{2} ≥ \frac{d}{(log m)^{3}} .  (129)

Inequality (129) tells us that (iii) applies immediately to give that

e(N ∩ W′, Y) ≤ Cp|Y | × αd′_{2}.  (130)

Putting (†)(iii), (125) and (130) together, we deduce that

\frac{γ}{2} × \frac{ηpdd′_{2}}{20(log m)^{2}} ≤ e(N ∩ W′, Y) ≤ Cαp|Y |d′_{2} ∼ Cαp\frac{ηdd′_{2}}{20(log m)^{2}} ,  (131)

which gives that γ/2 ≲ Cα, and hence, say,

α ≥ \frac{γ}{3C} .  (132)

We now describe briefly how the proof will proceed. Note that, because of (121), the expected cardinality 𝔼(|N ∩ W′|) of N ∩ W′ is at most 2εd′_{2}. Therefore, as ε is chosen a great deal smaller than γ/C, because of (132), the tail inequality for hypergeometric variables (Lemma 10) proves inequality (111) for the number of sets N satisfying Case 1 and with a given set Y = Y (N) (see Remarks 22 and 23). To complete the proof of this case, it suffices to notice that summing over all the possible Y contributes little enough to our estimate (see Remark 23). Let us turn to the detailed calculations.

We apply Lemma 10 to estimate the probability that |N ∩W′| should be as large as αd′_{2}, given that (132) holds. From (132), we have that

k(10) = αd′_{2} ≥ \frac{γ}{3C} d′_{2}.  (133)

Moreover, from (121) we know that

k(10) = λ(10) 𝔼(|N ∩ W′|) = λ(10)\frac{d′_{2}|W′|}{m_{2}} ≤ 2ελ(10)d′_{2}.  (134)

From (133) and (134) we obtain that

λ(10) ≥ \frac{γ}{6Cε}.  (135)

Therefore, Lemma 10 tells us that

ℙ(|N ∩ W′| ≥ αd′_{2}) ≤ (\frac{e}{λ})^{αd′_{2}} ≤ (\frac{6eCε}{γ})^{(γ/3C)d′_{2}} .  (136)

Thus, for a fixed set Y, the number of sets N with Y = Y (N) (see Remark 22) that fall into Case 1 is

≤ (\frac{6eCε}{γ})^{(γ/3C)d′_{2}} \binom{m_{2}}{d′_{2}}.  (137)

Now recall (118) in Remark 23. Using that d′_{2} ∼_{ε} d_{2}, and hence d_{2} ≤ d′_{2}/(1 − ε), we have that the total number of possible sets Y is bounded from above by

≤ (1 + o(1))^{d_{2}} ≤ 2^{d′_{2}}.  (138)

Finally, using (137) and (138) and recalling that ε ≤ ε_{0} (see (110)), where ε_{0} satisfies (109), we deduce that the total number of sets N is question is

≤ \{2 (\frac{6eCε}{γ})^{γ/3C}\}^{d′_{2}} \binom{m_{2}}{d′_{2}} ≤ (\frac{β_{1}}{2} )^{d′_{2}} \binom{m_{2}}{d′_{2}} ≤ \frac{1}{2}β_{1}^{d′_{2}} \binom{m_{2}}{d′_{2}}.  (139)

Inequality (139) shows that the bound in (111) does indeed hold in this case, and hence the proof of this case is finished.

Case 2. |D^{−}| ≥ (η/10)m_{1} Our aim is to show that the number of sets N as in the statement of the claim that fall in this case is

≤ \frac{1}{2}β_{1}^{d′_{2}} \binom{m_{2}}{d′_{2}}.  (140)

The proof of this statement is similar to the proof in Case 1 above, but somewhat simpler. We shall only give a brief outline of the proof. We first observe that a statement analogous to (†) may be proved in the same manner, except that we have, in this case, a set Y ⊂ D^{−} satisfying conditions (i)–(iii) of (†). We then estimate e(N, Y) in two ways. First, we observe that, because Y ⊂ D^{−}, we have

e(N, Y) ≤ (1 − γ)|Y |\frac{d′_{2}d_{2}}{m_{2}} .  (141)

However, we have

e(N, Y) ≥ ∑_{w∈N\W′} |Γ(w) ∩ Y | ≥ |N \ W′|(1 − 2ε)d̄_{Y} .  (142)

Comparing (141) and (142), we deduce that N \ W′ must be small, that is, the random set N must intersect the set W′ of exceptional vertices substantially. An application of the tail inequality for the hypergeometric distribution, Lemma 10, finishes the proof of this case.

This concludes the proof of Claim 14. □

4.1.3. Proof of the pair condition lemma, r.gs version. Here we use Lemma 12 to prove Theorem 13. The basic idea in the proof is the one discussed in Section 2: Lemma 12 shows that the family of ‘unwanted’ subgraphs in our random graph is thin, and hence a simple first moment calculation will tell us that such subgraphs do not occur in our random graphs almost surely (recall Remark 20).

Proof of Theorem 13. Let α and γ > 0 be given. We apply Lemma 12 with β(12) = α/4e, γ(12) = γ, and C(12) = 3/α. Lemma 12 gives us a constant ε(12) > 0. We claim that ε = αε(12)/2 will do in Theorem 13. Let us proceed to prove this claim.

We may and shall assume that our G = G(n, q) is such that the almost sure property specified in Lemma 8 is satisfied with δ = δ(8) = 1/2. In other words, we assume that

(*) if U and W are two disjoint sets of vertices of G with |U| and |W | ≫

q^{−1} log n, then

e(U, W) ∼_{1/2} q|U||W |.  (143)

Let us estimate the expected number of ‘counterexamples’ B = (U, W; E) ⊂ G with fixed m_{1} = |U|, m_{2} = |W |, and T = e(B). Observe that

p = \frac{e(B)}{m_{1}m_{2}} ≥ \frac{αe(G[U, W])}{m_{1}m_{2}} ≥ \frac{α}{2}q.  (144)

Thus, p^{2} min{m_{1}, m_{2}} ≥ (α^{2}/4)q^{2}m_{0} ≫ (log n)^{4} (see (88)) and hence (86), and therefore (82), are satisfied. We now observe that B = (U, W; E) is (ε(12), p)- regular, since it is (ε, q)-regular and (144) holds. Finally, we check that property ECB(U, W; C(12)) holds for B. Indeed, it suffices to apply (*) after observing that

q \frac{d}{(log m)^{3}} ≥ q \frac{pm}{(log n)^{3}} ≥ \frac{(α/2)q^{2}m}{(log n)^{3}} ≫ log n.  (145)

The discussion above tells us that a counterexample B ⊂ G is a member of the family of graphs whose cardinality is estimated in Lemma 12. Applying the estimate (85), we obtain that, for fixed m_{1}, m_{2}, and T, the expected number of such counterexamples is

≤ n^{m_{1}+m_{2}}β^{T} \binom{m_{1}m_{2}}{T}q^{T} ≤ n^{m_{1}+m_{2}} (\frac{eβm_{1}m_{2}}{T} q)^{T}

≤ n^{m_{1}+m_{2}} (eβ \frac{q}{p})^{T} ≤ n^{m_{1}+m_{2}} (\frac{2eβ}{α} )^{T} ≤ (\frac{2}{3})^{T} . (146)

Summing (146) over all possible m_{1}, m_{2}, and T, our result follows. □

4.2. A local condition for regularity. In this section, we state and prove a lemma that gives a sufficient condition for a possibly sparse bipartite graph to be ε-regular. The condition is local in nature. Similar results in somewhat different contexts have proved to be very useful; see [3, 4, 5, 9, 11, 17, 47, 48] and the proof of the upper bound in Theorem 15.2 in [15], due to J. H. Lindsey.

4.2.1. The statement of the lemma. Our lemma giving local conditions for the regularity of possibly sparse bipartite graphs is as follows.

Lemma 15 (The local condition lemma). For all ε > 0 and all C ≥ 1, there is δ > 0 such that any bipartite graph B = (U, W; E) satisfying properties

ChUB(U, W; δ, C), D(U, W; δ, ε) and PC(U, W; δ)  (147)

is ε-regular with respect to density p = e(U, W)/|U||W |, as long as p|U| ≥ 1/εδ.

Remark 24. Note that property ChUB(U, W; o(1), O(1)) is always satisfied in the dense case, and hence Lemma 15 above reduces to the well-known criterion for regularity that, in our language, asserts that properties D(U, W; o(1), o(1)) and PC(U, W; o(1)) imply o(1)-regularity.

We now state a result that guarantees the o(1)-regularity of ‘large’ bipartite subgraphs H = (U, W; E) of random graphs when H is known to satisfy property PC(U, W; o(1)). This result follows from Lemma 15.

Theorem 16 (The local condition lemma, r.gs version). Let 0 < q = q(n) < 1 and m_{0} = m_{0}(n) be such that

q^{2}m_{0} ≫ log n.  (148)

Then, for all α > 0 and all ε > 0, there is δ > 0 such that almost all random graphs G = G(n, q) satisfy the following property. Suppose U, W ⊂ V (G) with U ∩ W = ∅ and |U|, |W | ≥ m_{0} and F ⊂ E(G[U, W]) with T = |F | ≥ αe(G[U, W]) are such that H = (U, W; F) satisfies

D(U, W; δ, ε) and PC(U, W; δ).  (149)

Then the graph H = (U, W; F) is an ε-regular bipartite graph with respect to density ϱ = T/|U||W |.

4.2.2. Proof of the local condition lemma. Here we prove Lemma 15.

Proof of Lemma 15. Let 0 < ε < 1 and C ≥ 1 be given. Put

δ = \frac{ε^{5}}{7C} .  (150)

Note for later reference that, then, we have

\{\frac{δ}{ε} (6 + \frac{2C}{ε^{2}} )\}^{1/2} ≤ ε.  (151)

We shall now show that the choice for δ given in (150) will do.

Fix a bipartite graph B = (U, W; E) satisfying the hypothesis of our lemma. Let sets U′ ⊂ U and W′ ⊂ W with |U′| ≥ ε|U| and |W′| ≥ ε|W | be given. As usual, put m_{1} = |U| and m_{2} = |W |, p = T/m_{1}m_{2}, where T = e(B), and, also, let m′_{1} = |U′| and m′_{2} = |W′|. We aim at estimating the ‘error’

|e(U′, W′) − p|U′||W′||.  (152)

Let us define a matrix A = (a_{u,w}) whose elements are indexed by U × W. We put

a_{u,w} = \begin{cases}−(1 − p) & if \{u, w\} ∈ E(B) \\ p & otherwise. \end{cases}  (153)

Let

β_{w} = ∑{a_{u,w}: u ∈ U′}  (154)

and put b = (β_{w})_{w∈W}. We apply the Cauchy–Schwarz inequality to obtain that

∑_{w∈W} β_{w}^{2} ≥ ∑_{w∈W′} β_{w}^{2} ≥ \frac{1}{|W′|} ( ∑_{w∈W′} β_{w})^{2} .  (155)

Observe that

\begin{aligned}( ∑_{w∈W′} β_{w})^{2} & = ( ∑_{(u,w)∈U′×W′} a_{u,w})^{2} \\ & = \{−(1 − p)e(U′, W′) + p (m′_{1}m′_{2} − e(U′, W′))\}^{2} \\ & = \{pm′_{1}m′_{2} − e(U′, W′)\}^{2}, \end{aligned}  (156)

which is the square of the ‘error’ (152) that we wish to estimate. Now, on the other hand, we have

β_{w}^{2} = ( ∑_{u∈U′} a_{u,w})^{2} = ∑_{(u,u′)∈U′×U′} a_{u,w}a_{u′,w}.  (157)

Thus

∑_{w∈W} β_{w}^{2} = ∑_{(u,u′)∈U×U′} ∑_{w∈W} a_{u,w}a_{u′,w} = ∑_{(u,u′)∈U×U′}⟨a_{u}, a_{u′}⟩,  (158)

where a_{u} = (a_{u,w})_{w∈W} and similarly for a_{u′}. Let us consider the inner products in (158). Consider first the case in which u = u′. Writing d(x) = d_{B}(x) for the degree of a vertex x in B, we have, for any u ∈ U,

\begin{aligned}⟨a_{u}, a_{u}⟩ & = d(u)(1 − p)^{2} + (m_{2} − d(u))p^{2} \\ & = d(u)(1 − 2p + p^{2}) + (m_{2} − d(u))p^{2} \\ & = d(u)(1 − 2p) + m_{2}p^{2}. \end{aligned}  (159)

Suppose now that u ≠ u′ (u, u′ ∈ U). As usual, put d(x, y) = d_{B}(x, y) = |Γ_{B}(x) ∩ Γ_{B}(y)| for any two vertices x and y of B. Then

\begin{aligned}⟨a_{u}, a_{u′}⟩ & = (1 − p)^{2}d(u, u′) − p(1 − p)\{d(u) − d(u, u′) + d(u′) − d(u, u′)\} \\ & + p^{2}\{m_{2} − d(u) − d(u′) + d(u, u′)\} \\ & = d(u, u′) ((1 − p)^{2} + 2p(1 − p) + p^{2}) \\ & + d(u) (−p(1 − p) − p^{2}) + d(u′) (−p(1 − p) − p^{2}) + m_{2}p^{2} \\ & = d(u, u′) − (d(u) + d(u′))p + m_{2}p^{2}. \end{aligned} (160)

Putting (155), (156), (158), (159) and (160) together, we obtain that

\frac{1}{|W′|}\{pm′_{1}m′_{2} − e(U′, W′)\}^{2} = \frac{1}{|W′|} ( ∑_{w∈W′} β_{w})^{2}  (161)
≤ ∑_{(u,u′)∈U′×U′}⟨a_{u}, a_{u′}⟩  (162)
= ∑_{u∈U′} (d(u)(1 − 2p) + m_{2}p^{2})  (163)
+ ∑′_{(u,u′)} (d(u, u′) − (d(u) + d(u′))p + m_{2}p^{2}) , (164)

where ∑′_{(u,u′)} stands for sum over all pairs (u, u′) ∈ U′ × U′ with u ≠ u′. We now estimate the sums in (163) and (164) separately. We start with (164). Clearly,

∑′_{(u,u′)} (d(u, u′) − (d(u) + d(u′))p + m_{2}p^{2}) = Σ_{1} + Σ_{2},  (165)

where

Σ_{1} = ∑′_{(u,u′)} (d(u, u′) − m_{2}p^{2})  (166)

and

Σ_{2} = p ∑′_{(u,u′)} (2m_{2}p − (d(u) + d(u′))) .  (167)

To estimate Σ_{1}, we split the sum in (166) according to whether or not

\{u, u′\} ∈ F (δ) = F (U, W; δ) ⊂ \binom{U}{2}  (168)

(see (36)). Note that, because of property PC(U, W; δ) (cf. Definition 11), we know that

|F (δ)| = |F (U, W; δ)| ≤ δ\binom{|U|}{2} = δ\binom{m_{1}}{2}.  (169)

Since property ChUB(U, W; δ, C) holds (see (40)), relations (168) and (169) imply that

∑ {d(u, u′): {u, u′} ∈ F (δ)} ≤ Cδp^{2}m_{1}^{2}m_{2}.  (170)

Turning back to the estimate of Σ_{1} in (166), we use (170) to deduce that

\begin{aligned}Σ_{1} & = 2 ∑_{\{u,u′\}∉F (δ)} (d(u, u′) − m_{2}p^{2}) \\ & + 2 ∑_{\{u,u′\}∈F (δ)} (d(u, u′) − m_{2}p^{2}) \\ & ≤ 2δp^{2}m_{2}\binom{m′_{1}}{2} + 2 ∑_{\{u,u′\}∈F (δ)} d(u, u′) \\ & ≤ δp^{2}m_{2}(m′_{1})^{2} + 2Cδp^{2}m_{1}^{2}m_{2} \\ & ≤ (2C/ε^{2} + 1)δp^{2}(m′_{1})^{2}m_{2}, \end{aligned}  (171)

where in the last inequality we used that m′_{1} = |U′| ≥ ε|U| = εm_{1}. The estimation of Σ_{2} will be based on property D(U, W; δ, ε). We invoke D(U, W; δ, ε) to obtain that

(1 − δ)pm′_{1}m_{2} ≤ e(U′, W) ≤ (1 + δ)pm′_{1}m_{2}  (172)

(cf. (38)). Using (172), we see that

\begin{aligned}Σ_{2} & = p (2pm_{2}m′_{1}(m′_{1} − 1) − 2(m′_{1} − 1) ∑_{u∈U′} d(u)) \\ & = 2(m′_{1} − 1)p\{pm′_{1}m_{2} − e(U′, W)\} \\ & ≤ 2(m′_{1} − 1)p × δpm′_{1}m_{2} ≤ 2δp^{2}(m′_{1})^{2}m_{2}. \end{aligned}  (173)

It remains to estimate the sum in (163). We again use (172) to deduce that the sum in (163) is

(1 − 2p)e(U′, W) + m′_{1}m_{2}p^{2} ≤ (1 + δ)pm′_{1}m_{2} + m′_{1}m_{2}p^{2}

= \frac{1 + δ + p}{m′_{1}p}p^{2}(m′_{1})^{2}m_{2} ≤ \frac{3}{m′_{1}p}p^{2}(m′_{1})^{2}m_{2}. (174)

We now use that m′_{1} ≥ εm_{1} and that pm_{1} ≥ 1/εδ to conclude that the last term in (174) is

≤ \frac{3}{εm_{1}p}p^{2}(m′_{1})^{2}m_{2} ≤ 3δp^{2}(m′_{1})^{2}m_{2}.  (175)

Putting together (161)–(164) and (171)–(174), we have

\frac{1}{m′_{2}} \{pm′_{1}m′_{2} − e(U′, W′)\}^{2} ≤ (3δ + (\frac{2C}{ε^{2}} + 1) δ + 2δ) p^{2}(m′_{1})^{2}m_{2}.  (176)

Recalling the condition m′_{2} ≥ εm_{2} and inequality (151), we deduce that (152) is at most εpm′_{1}m′_{2}, and our proof is finished. □

4.2.3. Proof of the local condition lemma, r.gs version. Theorem 16 follows easily from Lemma 15.

Sketch of the proof of Theorem 16. Because of condition (148), we know that property ChUB(U, W; δ, C_{∧}) holds almost surely for C_{∧} = 2/α^{2} and any δ > 0. We pick δ = δ(ε, C_{∧}) > 0 as given by Lemma 15. The condition that p|U| ≥ εδ should hold is immediate. The hypotheses given in Lemma 15 for our bipartite graph B = (U, W; E) are now all satisfied, and the ε-regularity of B follows. □

4.3. The one-sided neighbourhood lemma. Our aim in this section is to prove a lemma concerning certain induced subgraphs of sparse ε-regular bipartite graphs. As always, we shall be interested in such ε-regular bipartite graphs that arise as subgraphs of r.gs. Roughly speaking, we show that almost every r.g. has the property that any large and dense enough ε-regular bipartite subgraph H = (U, W; F) of it is such that the neighbourhood Γ_{H}(w) of almost all vertices w ∈ W induces, together with W, an ε′-regular bipartite graph in H. Here, we may make ε′ > 0 as small as we wish by taking ε > 0 correspondingly small.

This somewhat long section is organized as follows. In Section 4.3.1, we state two auxiliary lemmas, Lemmas 17 and 18. In the following section, we state a counting version of the main result of Section 4.3, Lemma 19, and in the next section we state a consequence of the previous results concerning random graphs, cf. Theorem 20. All the proofs are given in the second part of Section 4.3. In Section 4.3.5, we give the proofs of Lemmas 17 and 18; in these proofs, we make use of an auxiliary lemma, Lemma 22, which is proved towards the end of Section 4.3.5. In Section 4.3.6, we give the proof of Lemma 19 and in the final section, Section 4.3.7, we are finally able to prove Theorem 20.

4.3.1. Statement of the one-sided neighbourhood lemma, auxiliary version. Let us describe the situation that is of our concern in this section. Suppose that we have a bipartite graph B on (U, W). We shall be interested in the following assertions, definitions, and notation concerning the bipartite graph B.

(I) |U| = m_{1}, |W | = m_{2}, T = e(B), p = T/m_{1}m_{2}, and d_{i} = pm_{i} (i ∈ {1, 2}). (II) (a) Property D(U, W; η_{0}, ε′) holds.

(b) Property PC(U, W; δ) holds. (III) (a) We write E(d′_{1}; η_{1}, C_{∧}) for the family of subsets U′ ⊂ U of cardinal-

ity d′_{1} for which ChUB(U′, W; η_{1}, C_{∧}) fails. Below, we shall be interested in d′_{1}-sets U′ with d′_{1} ∼_{σ′} d_{1}. We shall sometimes refer to the members of E(d′_{1}; η_{1}, C_{∧}) as the exceptional sets.

(b) Property ECB(U, W; C_{ECB}) holds. In particular, if Ū ⊂ U is such that |Ū| ≥ d/(log m)^{3}, then

e(Ū, W) ≤ C_{ECB}p|Ū||W |,  (177)

where, as before, d = min{d_{1}, d_{2}} and m = m_{+} = max{m_{1}, m_{2}}.

Our first auxiliary lemma concerns certain sets U′ ⊂ U that are ‘undesirable,’ given the set-up in (I)–(III) above. For constants σ > 0 and ε > 0, we consider the following properties for the set U′:

(a) ϱ = e(B[U′, W])/d′_{1}m_{2} ∼_{σ} p = T/m_{1}m_{2}.

(b) B[U′, W] is (ε, ϱ)-regular.

We let

I(d′_{1}; σ, ε) = {U′ ⊂ U: |U′| = d′_{1} and either (a) or (b) fails}.  (178)

Lemma 17 (One-sided neighbourhood lemma, auxiliary version). For all β > 0, ε > 0, σ > 0, 0 < σ′ < 1, C_{∧} > 0, and C_{ECB} > 0, there exist constants ε′ > 0, δ > 0, η_{0} > 0, and η_{1} > 0 such that if B satisfies properties (I)–(III) and d′_{1} ∼_{σ′} d_{1}, then

|I(d′_{1}; σ, ε) \ E(d′_{1}; η_{1}, C_{∧})| ≤ β^{d′_{1}} \binom{m_{1}}{d′_{1}},  (179)

provided that m_{1} ≫ 1/p^{2}.

Remark 25. Lemma 17 excludes from the family of sets that it counts the exceptional d′_{1}-sets U′ ⊂ U. Roughly speaking (and this may be seen in the proof of this lemma in Section 4.3.5), to assert (b) for a set U′, that is, the (ε, ϱ)- regularity of B[U′, W], we shall make use of the local condition lemma for regularity, Lemma 15. This lemma requires as a hypothesis property ChUB(U′, W; η_{1}, C_{∧}), which is guaranteed for non-exceptional sets U′ only (see (III)(a)).

For Lemma 17 to be useful later, we need to have some control on the number of exceptional sets. It turns out that a condition of the following form will apply when we make use of that lemma.

(III) (a′) For all U′ ⊂ U with d′_{1} = |U′| ∼_{σ′} d_{1}, we have that

for all F′ ⊂ \binom{U′}{2} such that |F′| ≤ η_{1}\binom{|U′|}{2},  (180)

we have

∑_{{x,y}∈F′} d_{W}^{B} (x, y) ≤ Qη_{1}p^{2}|U′|^{2}|W |,  (181)

where d_{W}^{B} (x, y) = |Γ_{B}(x) ∩ Γ_{B}(y)|.

In (III)(a′) above, Q is some constant independent of n. Probably only the extremely meticulous reader will notice the difference between properties (III)(a′) and ChUB(U′, W; η_{1}, Q), since the difference is quite subtle. In (III)(a′), the density (squared) appearing on the right-hand side of (181) is p = e(B)/|U||W |. Property ChUB(U′, W; η_{1}, Q) would require this to be ϱ = e(B[U′, W])/|U′||W |, which may be smaller than p.

The whole point of Lemma 18 below is to show that ϱ is not a great deal smaller than p for an overwhelming proportion of the sets U′ ⊂ U. Therefore, we are able to conclude that, with very high probability, property ChUB(U′, W; η_{1}, Q′) does hold for some constant Q′ > Q if (III)(a′) holds. In other words, Lemma 18 tells us that a bipartite graph B = (U, W; E) as in the statement of Lemma 17 has very few exceptional sets if (III)(a′) above holds.

To be more precise, we assume that assertions (I), (II)(a), (III)(a′) and (b) apply to our bipartite graph B = (U, W; E) (condition (II)(b) is not required). We claim that, then,

|E(d′_{1}; η_{1}, Q′)| ≤ β_{exc}^{d′_{1}}\binom{m_{1}}{d′_{1}}  (182)

holds for any given Q′ > Q and β_{exc} > 0, as long as ε′ > 0 and η_{0} > 0 are suitably small. Formally, we have the following lemma.

Lemma 18. For any β_{exc} > 0, Q ≥ 1, σ > 0, σ′ > 0, η_{1} > 0, and C_{ECB} > 0, there exist ε′ > 0 and η_{0} > 0 such that the following assertion holds. If B = (U, W; E) is a bipartite graph for which (I), (II)(a), (III)(a′) and (b) apply, then inequality (182) holds for all d′_{1} ∼_{σ′} d_{1} with Q′ = Q/(1 − σ)^{2}.

4.3.2. Statement of the one-sided neighbourhood lemma, counting version. We now turn to a corollary of Lemma 17 in Section 4.3.1. In fact, Lemma 17 has as a consequence a lemma that estimates the number of certain bipartite graphs. Roughly speaking, in our next lemma we consider graphs B = (U, W; E) satisfying (I)–(III) above that have many vertices w ∈ W whose neighbourhood Γ(w) ⊂ U induces together with W a graph that is not dense enough or, else, is not regular enough. Unfortunately, we are actually able to prove a result that is technically somewhat more cumbersome. Let us turn to the precise statement of the result that we shall prove.

Let B = (U, W; E) be a bipartite graph for which (I), (II)(a) and (b), and (III)(a) and (b) above apply. In fact, we shall further require the following condition:

(III) (a′′) For all d′_{1} ∼_{σ′} d_{1}, we have have

|E(d′_{1}; η_{1}, C_{∧})| ≤ β_{exc}^{d′_{1}}\binom{m_{1}}{d′_{1}}.  (183)

In (III)(a′′) above, β_{exc} is some small positive constant independent of n. This technical condition will be required because Lemma 17 excludes the exceptional sets from the estimate in (179) (see Remark 25).

We now let W′ be a new set of vertices, with W′ ∩ (U ∪ W) = ∅. We suppose that we have a bipartite graph B′ = (U, W′; E′). In applications later, we shall consider the bipartite graph H = B ∪ B′ = (U, W ∪ W′; E ∪ E′).

Let m′ = |W′| and T′ = e(B′), and suppose that

m′ ≥ ν(|W | + |W′|) = ν(m_{2} + m′).  (184)

Furthermore, assume that

p′ = \frac{T′}{m_{1}m′} ∼_{σ′} p,  (185)

and suppose that for at least m′/2 vertices w′ ∈ W′, we have

d_{B′}(w′) = |Γ_{B′}(w′)| ∼_{σ′} d_{1} = pm_{1}. (186)

We may think of (184)–(186) as ‘compatibility’ conditions for B′ with respect to B. Now let Ũ = Ũ(w′) = Γ_{B′}(w′). We say that w′ ∈ W′ satisfying the degree condition in (186) is (ε, σ, σ′; B, B′)-bad, or simply bad, if

Ũ = Ũ(w′) = Γ_{B′}(w′) ∈ I(d′_{1}; σ, ε) ∪ E(d′_{1}; η_{1}, C_{∧})  (187)

(recall the definitions of these families of sets given in (178) and (III)(a)). For clarity, let us state explicitly the conditions required for a vertex w′ ∈ W′ to be bad:

(a) either ϱ_{w′} = e(B[Ũ, W])/|Ũ||W | ∼_{σ} p = T/m_{1}m_{2} fails to hold,

(b) or B[Ũ, W] is not (ε, ϱ_{w′})-regular,

(c) or else Ũ ∈ E(|Ũ|; η_{1}, C_{∧}), that is, ChUB(Ũ, W; η_{1}, C_{∧}) fails to hold. Let us now state the property of our current concern.

(IV) The number of (ε, σ, σ′; B, B′)-bad vertices w′ ∈ W′ is at least μm′.

We are now ready to state our next lemma.

Lemma 19 (One-sided neighbourhood lemma, counting version). For all β > 0, ε > 0, μ > 0, ν > 0, σ > 0, 0 < σ′ < 1, C_{∧} > 0, and C_{ECB} > 0, there exist constants β_{exc} > 0, ε′ > 0, δ > 0, η_{0} > 0, and η_{1} > 0, such that the number of pairs of compatible bipartite graphs (B, B′), on fixed sets U, W, and W′, satisfying properties (I), (II)(a) and (b), (III)(a′′) and (b) and (IV) is

≤ βT̃\binom{m_{1}(m′ + m_{2})}{T̃},  (188)

where T̃ = e(B) + e(B′), as long as T̃ ≫ m′ log m′.

Remark 26. For any given constants ε, μ, ν, σ, σ′, C_{∧}, C_{ECB}, β_{exc}, ε′, δ, η_{0}, and η_{1} and any function ω = ω(m′) with ω → ∞ as m′ → ∞, we may define the family of bipartite graphs H that arise as the union B ∪ B′ for the pairs (B, B′) that are counted in Lemma 19 with these parameters (ω is used to define an explicit lower bound for T̃; that is, we require that T̃ ≥ ωm′ log m′). For each possible order (m_{1}, m_{2} + m′) of H, we assume that all these graphs H are on some pair of fixed vertex classes (U_{0}, W_{0}). Let

H(U_{0}, W_{0}, ω; ε, μ, ν, σ, σ′, C_{∧}, C_{ECB}, β_{exc}, ε′, δ, η_{0}, η_{1})  (189)

be the family of such graphs H.

Recall Definition 9 and Remark 10 from Section 2. Lemma 19 implies immediately that the family in (189) is β-thin, as long as β_{exc} > 0, ε′ > 0, δ > 0, η_{0} > 0, and η_{1} > 0 are suitably small.

Finally, we observe that calculations analogous to the ones in the proof of Lemma 6 will show that, roughly speaking, random graphs almost surely do not contain ‘large’ subgraphs isomorphic to the members of the family in (189) (cf. Theorem 20).

4.3.3. Statement of the one-sided neighbourhood lemma, r.gs version. We shall now state a result concerning random graphs that may be derived from Lemmas 18 and 19. It will be convenient to have the following piece of notation to state our result.

In the next definition, 0 < q < 1 will usually be the edge probability of the random graph under consideration, m_{0} will be the ‘size lower bound’ as in (27), and α, ε, σ, σ′, μ, ν, and ε′ will be small positive constants.

Definition 27 (N (q, m_{0}; α, ε, σ, σ′, μ, ν; ε′)). Given a graph G, we say that property N (q, m_{0}; α, ε, σ, σ′, μ, ν; ε′) holds for G if the following statement is true: suppose H = (U, W; F) ⊂ G is a bipartite subgraph of G and W = W′ ∪ W′′ is a partition of W for which the following assertions hold:

(1) |U| = m_{1}, |W | = m_{2}, where m_{1}, m_{2} ≥ m_{0}, and |F | ≥ αe(G[U, W]),

(2) H = (U, W; F) is an ε′-regular bipartite graph with respect to density q,

(3) m′_{2} = |W′| ≥ νm_{2} and m′′_{2} = |W′′| ≥ νm_{2}. Then, putting p = e(H)/|U||W | = |F |/m_{1}m_{2} and H′ = H[U, W′] and H′′ = H[U, W′′], we have that for at least (1 − μ)m′_{2} vertices w′ ∈ W′ the following assertion holds:

(4) if Ũ = Γ_{H′}(w′) = Γ_{H}(w′) and H(w′) = H′′[Ũ, W′′] = H[Ũ, W′′], then

(i) d_{H′}(w′) = |Ũ| ∼_{σ′} d_{1} = pm_{1},

(ii) ϱ(w′) = e(H(w′))/|Ũ||W′′| ∼_{σ} p,
(iii) H(w′) is (ε, ϱ(w′))-regular.

Remark 28. It may be worth noting that having property N (q, m_{0}; α, ε, σ, σ′, μ, ν; ε′) above is essentially equivalent to not containing subgraphs isomorphic to members of the family in (189). Given that this family is thin (see Remark 26), Theorem 20 below follows from calculations similar to the ones in Lemma 6.

Theorem 20 (One-sided neighbourhood lemma, r.gs version). Let 0 < q = q(n) < 1 and m_{0} = m_{0}(n) be such that

q^{3}m_{0} ≫ log n and q^{2}m_{0} ≫ (log n)^{4}.  (190)

Then, for all α > 0, ε > 0, σ > 0, 0 < σ′ < 1, μ > 0 and ν > 0, there is ε′ > 0 such that almost every G = G(n, q) satisfies property N (q, m_{0}; α, ε, σ, σ′, μ, ν; ε′).

4.3.4. A two-sided neighbourhood lemma. In this section, we state a ‘two-sided’ version of Theorem 20. Recall that in property N (q, m_{0}; α, ε, σ, σ′, μ, ν; ε′) (see Definition 27), we consider the graph H(w′) = H[Ũ, W′′], induced in H between W′′ and the neighbourhood Ũ = Γ_{H}(w′) of the vertices w′ ∈ W′ in H = (U, W; F), where W = W′ ∪ W′′ is some fixed partition of W.

We are now interested in considering the bipartite graphs that are induced between two neighbourhoods in H, namely, the neighbourhoods Ũ = Γ_{H}(w′) (w′ ∈ W′) as before and the neighbourhoods W̃ = Γ_{H}(u′), where u′ ∈ U′ and U = U′∪U′′ is some fixed partition of U (for technical reasons, we shall in fact consider the ‘restricted’ neighbourhoods Γ_{H}(w′) ∩ U′′ and Γ_{H}(u′) ∩ W′′). To make this precise, we introduce property N_{2}(q, m_{0}; α, ε, σ, σ′, μ, ν; ε′), a property whose definition follows closely the definition of property N (q, m_{0}; α, ε, σ, σ′, μ, ν; ε′) (see Definition 27).

In Definition 29 below, the reader may think of 0 < q < 1 as the edge probability of a random graph under consideration. The quantity m_{0} is the ‘size lower bound’ as in (27), and α, ε, σ, σ′, μ, ν, and ε′ are small positive constants.

Definition 29 (N_{2}(q, m_{0}; α, ε, σ, σ′, μ, ν; ε′)). Given a graph G, we say that property N_{2}(q, m_{0}; α, ε, σ, σ′, μ, ν; ε′) holds for G if the following statement is true: suppose H = (U, W; F) ⊂ G is a bipartite subgraph of G and

U = U′ ∪ U′′ and W = W′ ∪ W′′  (191)

are partitions of U and W for which the following assertions hold:

(1) |U| = m_{1}, |W | = m_{2}, where m_{1}, m_{2} ≥ m_{0}, and |F | ≥ αe(G[U, W]),

(2) H = (U, W; F) is an ε′-regular bipartite graph with respect to density q,

(3) (a) m′_{1} = |U′| ≥ νm_{1} and m′′_{1} = |U′′| ≥ νm_{1},

(b) m′_{2} = |W′| ≥ νm_{2} and m′′_{2} = |W′′| ≥ νm_{2}. Put p = e(H)/|U||W | = |F |/m_{1}m_{2}. Moreover, for each pair of vertices u′ ∈ U′ and w′ ∈ W′ , let

H(u′, w′) = H[Γ_{H}(w′) ∩ U′′, Γ_{H}(u′) ∩ W′′]  (192)

be the bipartite graph induced between the ‘restricted’ neighbourhoods Γ_{H}(w′)∩U′′ and Γ_{H}(u′) ∩ W′′ of w′ and u′. Then, for at least (1 − μ)m′_{1} vertices u′ ∈ U′ and for at least (1 − μ)m′_{2} vertices w′ ∈ W′, the following assertion holds:

(4) let Ũ = Γ_{H}(w′) ∩ U′′ and W̃ = Γ_{H}(u′) ∩ W′′. Then
(i) |Ũ| ∼_{σ′} d′′_{1} = pm′′_{1} and |W̃| ∼_{σ′} d′′_{2} = pm′′_{2},

(ii) ϱ(H(u′, w′)) = e(H(u′, w′))/|Ũ||W̃| ∼_{σ} p,
(iii) H(u′, w′) is (ε, ϱ(H(u′, w′)))-regular.

We are now able to state our two-sided neighbourhood lemma for random graphs.

Theorem 21 (Two-sided neighbourhood lemma, r.gs version). Let 0 < q = q(n) < 1 and m_{0} = m_{0}(n) be such that

q^{3}m_{0} ≫ log n and q^{2}m_{0} ≫ (log n)^{4}.  (193)

Then, for all α > 0, ε > 0, σ > 0, 0 < σ′ < 1, μ > 0 and ν > 0, there is ε′ > 0 such that almost every G = G(n, q) satisfies property N_{2}(q, m_{0}; α, ε, σ, σ′, μ, ν; ε′).

We shall prove Theorem 21 in [31].

4.3.5. Proof of the one-sided neighbourhood lemma, auxiliary version. Our aim in this section is to prove Lemmas 17 and 18. We start with a technical but simple lemma. Suppose B = (U, W; E) is a bipartite graph satisfying (I) from Section 4.3.1. Suppose further that

(i) property D(U, W; η, ε) holds, (ii) for all Ū ⊂ U such that |Ū| ≥ d/(log m)^{3}, we have

e(Ū, W) ≤ Cp|Ū||W |,  (194)

where d and m are as in (III)(b). We would then like to say that, with extremely high probability, a d′_{1}-set U′ ⊂ U, where d′_{1} ∼_{σ′} d_{1}, chosen uniformly at random from all such sets, is such that

(iii) p′ = e(U′, W)/|U′||W | ∼_{σ} p, and (iv) D(U′, W; η′, ε′) holds,

where σ > 0, η′ > 0, and ε′ > 0 are small constants. To be more precise, we have the following lemma.

Lemma 22. For all β > 0, η′ > 0, ε′ > 0, σ > 0, 0 < σ′ < 1, and C ≥ 1, there exist η > 0 and ε > 0 such that, if (i) and (ii) hold and d′_{1} ∼_{σ′} d_{1}, then the number of d′_{1}-sets U′ ⊂ U failing either (iii) or (iv) is

≤ β^{d′_{1}} \binom{m_{1}}{d′_{1}}.  (195)

The fairly straightforward proof of Lemma 22, which is based on the hypergeometric tail lemma (Lemma 10), is postponed to the end of Section 4.3.5.

Proof of Lemma 17. The proof will be based on Lemmas 11, 15, and 22. Let β, ε, σ, σ′, C_{∧}, and C_{ECB} as in the statement of Lemma 17 be given. Invoke Lemma 15 with parameters ε(15) = ε and C(15) = C_{∧}. Lemma 15 then gives us a constant δ(15) > 0. Here we are following the convention of Remark 7. Since we have a stronger statement for smaller values of σ, we may and shall assume that

σ ≤ \frac{1}{7}δ(15).  (196)

We now invoke Lemma 11 with α(11) = δ(15) and β(11) = β/2, and obtain the constant η_{0}(11). Let us now apply Lemma 22 to constants β(22) = β/2, η′(22) = δ(15), ε′(22) = ε, σ(22) = σ, σ′(22) = σ′, and C(22) = C_{ECB}. Lemma 22 then gives us constants η(22) > 0 and ε(22) > 0.

Finally, we put ε′ = ε(22),

δ = min \{\frac{1}{7}δ(15), η_{0}(11)\} ,  (197)

η_{0} = η(22), and η_{1} = δ(15).

Claim 23. This choice for ε′, δ, η_{i} (i ∈ {0, 1}) will do in Lemma 17.

Proof. To prove this claim, we select, uniformly at random, a d′_{1}-set U′ ⊂ U, and estimate the probability that either (a) or (b) in the definition of I(d′_{1}; σ, ε) fails to hold, assuming that U′ ∉ E(d′_{1}; η_{1}, C_{∧}). We start by invoking Lemma 22. Condition (II)(a) tells us that property D(U, W; η_{0}, ε′) = D(U, W; η(22), ε(22)) holds, and hence condition (i) in Lemma 22 holds. Moreover, condition (III)(b) tells us that hypothesis (ii) of Lemma 22 is satisfied with C(22) = C_{ECB}. Lemma 22 then tells us that, with probability ≥ 1 − β_{exc}(22)^{d′_{1}} ≥ 1 − (1/2)β^{d′_{1}}, we have that

property D(U′, W; η′(22), ε′(22)) = D(U′, W; δ(15), ε) holds,  (198)

and that

ϱ = \frac{e(B[U′, W])}{|U′||W |} ∼_{σ(22)} p.  (199)

Note that (199) means that

ϱ ∼_{σ} p,  (200)

since σ(22) = σ. We assume henceforth that (198)–(200) hold. Recall now that, by (II)(b),

property PC(U, W; δ) holds.  (201)

Consider

F = F (U, W; δ) ⊂ \binom{U}{2},  (202)

and think of F as a graph on the vertex set U; in particular, write F [U′] for the graph induced by U′. In view of the fact that δ ≤ η_{0}(11) (see (197)) and (201), an application of Lemma 11 gives that

ℙ (e(F [U′]) ≥ α(11)\binom{d′_{1}}{2}) ≤ β(11)^{d′_{1}} ≤ \frac{1}{2}β^{d′_{1}}.  (203)

We claim that if

e(F [U′]) < α(11)\binom{d′_{1}}{2}  (204)

holds, then

property PC(U′, W; δ(15)) holds.  (205)

For convenience, put δ′ = δ/7. In order to verify this claim, we first assert that

(1 − δ(15))ϱ^{2}m_{2} ≤ (1 − δ′)p^{2}m_{2} ≤ (1 + δ′)p^{2}m_{2} ≤ (1 + δ(15))ϱ^{2}m_{2}.  (206)

Let us check (206). Using (200), we deduce that

(1 − δ(15))ϱ^{2} ≤ (1 − δ(15))(1 + σ)^{2}p^{2} ≤ (1 − δ(15))(1 + 3σ)p^{2}

≤ (1 − δ(15) + 3σ)p^{2} ≤ (1 − \frac{4}{7}δ(15)) p^{2} ≤ (1 − δ′)p^{2}. (207)

Moreover, again using (200), we have

(1 + δ′)p^{2} ≤ (1 + δ′)\frac{ϱ^{2}}{(1 − σ)^{2}} ≤ (1 + δ′)(1 + 3σ)ϱ^{2}

= (1 + δ′ + 3σ + 3σδ′)ϱ^{2} ≤ (1 + δ′ + 6σ)ϱ^{2} ≤ (1 + δ(15))ϱ^{2}. (208)

Inequalities (207) and (208) show that (206) does indeed hold. Now, (206) implies that

F (U′, W; δ(15)) ⊂ F (U, W; δ′) ⊂ F (U, W; δ).  (209)

However, (202), (204), and (209) implies that

|F (U′, W; δ(15))| ≤ α(11)\binom{d′_{1}}{2}.  (210)

Since α(11) = δ(15), relation (210) means that

property PC(U′, W; δ(15)) holds.  (211)

Since (204) holds with probability ≥ 1 − β(11)^{d′_{1}} ≥ 1 − (1/2)β^{d′_{1}} (see (203)), we have that (211) holds with this probability. We assume from now on that (211) does hold. We have to show that B[U′, W] is (ε, ϱ)-regular.

Since we are assuming that U′ ∉ E(d′_{1}; η_{1}, C_{∧}), we know that

ChUB(U′, W; η_{1}, C_{∧}) = ChUB(U′, W; δ(15), C(15)) holds.  (212)

We now observe that

ϱ|U′| ≥ \frac{1}{ε(15)δ(15)} = \frac{1}{εδ(15)},  (213)

since we assume that |U| = m_{1} ≫ 1/p^{2}. We are now in position to apply Lemma 15 to B[U′, W]. Because of (198), (211), (212), and (213), by Lemma 15 we have that B[U′, W] is (ε, ϱ)-regular. This finishes the proof of Claim 23. □

The proof of Lemma 17 is complete. □

Half of the proof of Lemma 18 is in fact contained in the proof of Lemma 17 above.

Proof of Lemma 18. The proof of this lemma will be based on Lemma 22. Let constants β_{exc}, Q, σ, σ′, η_{1}, and C_{ECB} as in the statement of Lemma 18 be given. We invoke Lemma 22 with constants β(22) = β_{exc}, η′(22) = ε′(22) = 1 (in fact, we do not care about conclusion (iv) in Lemma 22), σ(22) = σ, σ′(22) = σ′, and C(22) = C_{ECB}. Then, Lemma 22 gives us constants η(22) > 0 and ε(22) > 0. We let η_{0} = η(22) and ε′ = ε(22), and claim that this choice for η_{0} and ε′ will do in Lemma 18.

Thus, let B = (U, W; E) be as in the statement of Lemma 18 and, as in the proof Lemma 17, let U′ be a random d′_{1}-subset of U. We shall estimate the probability that

ChUB(U′, W; η_{1}, Q/(1 − σ)^{2})  (214)

fails.

By conditions (I), (II)(a), (III)(b), and the choice of the constants, we may deduce from Lemma 22 that inequality (199) holds with probability 1 − β_{exc}^{d′_{1}}. We now assume that (199) holds and we prove that (214) follows. Clearly, this suffices to prove Lemma 18.

To verify (214), we let F′ ⊂ \binom{U′}{2} with |F′| ≤ η_{1}\binom{|U′|}{2} be fixed. Then, by (III)(a′), we have

∑_{\{x,y\}∈F′} d_{W}^{B} (x, y) ≤ Qη_{1}p^{2}|U′|^{2}|W | ≤ \frac{Q}{(1 − σ)^{2}} η_{1}ϱ^{2}|U′|^{2}|W |,  (215)

where we used that p ≤ ϱ/(1−σ), which follows from (199). Thus (214) does follow and Lemma 18 is proved. □

Proof of Lemma 22. Let β > 0, η′ > 0, ε′ > 0, σ > 0, 0 < σ′ < 1, and C ≥ 1 be given. It turns out that it will be convenient to have that

σ ≤ \frac{1}{3}η′.  (216)

One easily sees that we may assume (216), since the smaller σ is, the stronger is the result that we get. Also, we set

η′′ = \frac{1}{3}η′.  (217)

Let α > 0 and η > 0 be small enough so that we have

η + Cα ≤ σ and η + \frac{Cα}{ε′} ≤ η′′.  (218)

Let now U′ ⊂ U be a set of cardinality d′_{1} chosen uniformly at random, where d′_{1} ∼_{σ′} d_{1}. Let ε = ε(α, β) > 0 be small enough so that if X ⊂ U is a fixed set such that |X| ≤ 2ε|U|, then

ℙ(|U′ ∩ X| > α|U′|) < β^{d′_{1}}.  (219)

The existence of such a constant ε > 0 follows from Lemma 10. We claim that this choice of η and ε will do. To verify this claim, suppose conditions (i) and (ii) hold for our bipartite graph B = (U, W; E).

Let us now consider property (iii). Let

X = {x ∈ U: |d_{W}^{B} (x) − p|W || > ηp|W |} .  (220)

Because of property D(U, W; η, ε), we have that |X| < 2ε|U|. Because of our choice of ε > 0, we know that (219) holds. In the remainder of the proof, we show that properties (iii) and (iv) do hold if we have

|U′ ∩ X| ≤ α|U′|.  (221)

In view of (219), this will complete the proof of Lemma 22. Thus, let us assume that (221) holds. To estimate e(U′, W), observe that

e(U′, W) = e(U′ \ X, W) + e(U′ ∩ X, W).  (222)

We have

e(U′ \ X, W) ≤ (1 + η)p|U′ \ X||W | ≤ (1 + η)p|U′||W |.  (223)

On the other hand, extending U′ ∩ X to a set Ū ⊂ U of cardinality α|U′| ≥ d/(log m)^{3} arbitrarily, we have, by condition (ii) in the set-up for Lemma 22, that

e(U′ ∩ X, W) ≤ e(Ū, W) ≤ Cpα|U′||W |.  (224)

Putting together (222), (223), and (224), we have

e(U′, W) ≤ (1 + η)p|U′||W | + Cαp|U′||W |

≤ (1 + η + Cα)p|U′||W | ≤ (1 + σ)p|U′||W |, (225)

where we used (218) for the last inequality. Also, we have

e(U′, W) ≥ e(U′ \ X, W) ≥ (1 − η)p|U′ \ X||W | ≥ (1 − η)(1 − α)p|U′||W |

≥ (1 − (η + α))p|U′||W | ≥ (1 − σ)p|U′||W |, (226)

where again we used (218). Inequalities (225) and (226) mean that e(U′, W) ∼_{σ} p|U′||W |. Thus we have deduced that condition (iii) of our lemma holds if (221) is verified.

Let us now show that (iv) is also implied by (221). Let Ũ′ ⊂ U′ with |Ũ′| ≥ ε′|U′| be given. Then

|Ũ′ ∩ X| ≤ |U′ ∩ X| ≤ α|U′| ≤ \frac{α}{ε′} |Ũ′|.  (227)

We have

e(Ũ′ \ X, W) ≤ (1 + η)p|Ũ′ \ X||W | ≤ (1 + η)p|Ũ′||W |.  (228)

Moreover,

e(Ũ′ ∩ X, W) ≤ e(Ū, W) ≤ Cp|Ū||W | ≤ Cp\frac{α}{ε′} |Ũ′||W |,  (229)

where Ū ⊂ U′ is an arbitrary subset of U′ with Ũ′ ∩ X ⊂ Ū and |Ū| = α|U′| ≥ d/(log m)^{3}. Note that the last inequality in (229) follows from |Ū| = α|U′| ≤ (α/ε′)|Ũ′|. Summing (228) and (229), we obtain

e(Ũ′, W) ≤ (1 + η)p|Ũ′||W | + \frac{Cα}{ε′}p|Ũ′||W |

≤ (1 + η + \frac{Cα}{ε′}) p|Ũ′||W | ≤ (1 + η′′)p|Ũ′||W |, (230)

where for the last inequality we used (218). Finally, using (227) and (218), we observe that

e(Ũ′, W) ≥ e(Ũ′ \ X, W) ≥ (1 − η)p|Ũ′ \ X||W | ≥ (1 − η) (1 − \frac{α}{ε′} ) p|Ũ′||W |

≥ (1 − η − \frac{α}{ε′} ) p|Ũ′||W | ≥ (1 − η′′)p|Ũ′||W |. (231)

Inequalities (230) and (231) mean that

e(Ũ′, W) ∼_{η′′} p|Ũ′||W |.  (232)

Using that

p′ = \frac{e(U′, W)}{|U′||W |} ∼_{σ} p,  (233)

which we already know follows from (221), we shall deduce from (232) that

e(Ũ′, W) ∼_{η′} p′|Ũ′||W |.  (234)

Note that, then, we shall have proved that condition (iv) does follow from (221), and hence the proof Lemma 22 will be complete. Let us prove (234).

We claim that

(1 − η′)p′ ≤ (1 − η′′)p ≤ (1 + η′′)p ≤ (1 + η′)p′,  (235)

and note that this claim suffices to show that (234) follows from (232). Let us therefore check (235). Since (233) holds and we have (216) and (217), we see that

(1 − η′)p′ ≤ (1 − η′)(1 + σ)p ≤ (1 − η′ + σ)p ≤ (1 − η′′)p.  (236)

Moreover, again by (233), (216), and (217) we have that

(1 + η′)p′ ≥ (1 + η′)(1 − σ)p = (1 + η′ − σ − ση′)p

≥ (1 + η′ − 2σ)p ≥ (1 + η′′)p. (237)

Inequalities (236) and (237) show that (235) does indeed hold. The proof of Lemma 22 is complete. □

4.3.6. Proof of the one-sided neighbourhood lemma, counting version. The proof of Lemma 19 will be based on repeated applications of Lemma 17.

Proof of Lemma 19. Let β, ε, μ, ν, σ, σ′, C_{∧}, and C_{ECB} as in the statement of the lemma be given. Let β_{0} > 0 be a constant such that

β_{0}^{(1/2)νμ(1−σ′)^{3}} ≤ \frac{1}{2}β.  (238)

For later reference, observe that

β_{0}^{(1/2)μ(1−σ′)^{2}} ≤ \frac{1}{2}β,  (239)

since ν(1 − σ′) ≤ 1. Let

β(17) = β_{exc} = \frac{1}{2}β_{0}.  (240)

Let also ε(17) = ε, σ(17) = σ, σ′(17) = σ′, C_{∧}(17) = C_{∧}, and C_{ECB}(17) = C_{ECB}. Lemma 17 then asserts the existence of the constants ε′ = ε′(17), δ = δ(17), η_{0} = η_{0}(17), and η_{1} = η_{1}(17). We claim that these constants ε′, δ, η_{0}, and η_{1} will do in Lemma 19. We now proceed to prove this claim.

Recall that we aim at estimating the number of pairs (B, B′) of graphs satisfying the properties given in the statement of Lemma 19. We estimate the number of graphs B in such pairs (B, B′) by the trivial bound

≤ \binom{m_{1}m_{2}}{T}.  (241)

We now fix a graph B and generate the graphs B′ for which (B, B′) is a valid pair by randomly selecting the neighbourhood sets of the vertices w′ ∈ W′ in U. To be more precise, pick first a partition d = (f_{i})_{1≤i≤m′} of T′, and suppose that d(w′_{i}) = d_{U}^{B′}(w′_{i}) = f_{i}, where W′ = {w′_{1}, …, w′_{m′}}. Consider only the degree sequences d such that for at least m′/2 indices i we have f_{i} ∼_{σ′} d_{1} = pm_{1} (cf. (186)). We now generate B′ by picking an element (Ũ_{i})_{1≤i≤m′} from

∏_{1≤i≤m′} \binom{U}{f_{i}}  (242)

uniformly at random, and letting Γ_{B′}(w′_{i}) = Ũ_{i} for all 1 ≤ i ≤ m′. We now apply Lemma 17 and property (III)(a′′). Given a vertex w′_{i} ∈ W′, note that w′_{i} will be a (ε(17), σ(17), σ′(17); B, B′)-bad vertex if and only if f_{i} ∼_{σ′} d_{1} = pm_{1} and its neighbourhood Ũ_{i} = Γ_{B′}(w′_{i}) ⊂ \binom{U}{f_{i}} satisfies

Ũ_{i} ∈ I(f_{i}; σ(17), ε(17)) ∪ E(f_{i}; η_{1}(17), C_{∧}(17))  (243)

(cf. (187)). Thus, assuming that f_{i} ∼_{σ′} d_{1} = pm_{1}, the number of choices for the neighbourhood of w′_{i} that makes w′_{i} a (ε(17), σ(17), σ′(17); B, B′)-bad vertex is, by Lemma 17 and property (III)(a′′),

|I(f_{i}; σ(17), ε(17)) ∪ E(f_{i}; η_{1}(17), C_{∧}(17))|

≤ β(17)^{f_{i}} \binom{U}{f_{i}} + β_{exc}^{f_{i}}\binom{U}{f_{i}} = (β(17)^{f_{i}} + β_{exc}^{f_{i}}) \binom{U}{f_{i}}. (244)

Since we choose an element from (242) uniformly at random to generate B′ and the events that w′_{i} should be (ε(17), σ(17), σ′(17); B, B′)-bad (1 ≤ i ≤ m′) are independent, we see that the probability that (IV) holds is at most

∑_{W′′} ∏_{w′_{i}∈W′′} (β(17)^{f_{i}} + β_{exc}^{f_{i}}) ≤ ∑_{W′′} ∏_{w′_{i}∈W′′} β_{0}^{f_{i}},  (245)

where the sum is over all

W′′ ⊂ W^{∗} = {w′_{i}: f_{i} ∼_{σ′} d_{1} = pm_{1}}  (246)

with |W′′| ≥ μm′. Now note that

d_{1}m′ = pm_{1}m′ = \frac{p}{p′} p′m_{1}m′ ≥ \frac{1}{1 + σ′} T′ ≥ (1 − σ′)T′,  (247)

since (185) holds. Therefore, we have that (245) is

≤ 2^{m′}β_{0}^{μ(1−σ′)d_{1}m′} ≤ 2^{m′}β_{0}^{μ(1−σ′)^{2}T′}.  (248)

Summing over all possible degree sequences d = (f_{i})_{1≤i≤m′}, we deduce that the number of graphs B′ valid for a fixed graph B is

≤ \binom{T′ + m′ − 1}{m′ − 1}2^{m′}β_{0}^{μ(1−σ′)^{2}T′} \binom{m_{1}m′}{T′}.  (249)

However, we deduce from (184) and (185) that

T′ ≥ (1 − σ′)T \frac{m_{1}m′}{m_{1}m_{2}} ≥ ν(1 − σ′)T.  (250)

Inequality (250) implies that the quantity in (249) is

≤ \binom{T′ + m′ − 1}{m′ − 1}2^{m′}β_{0}^{(1/2)νμ(1−σ′)^{3}T +(1/2)μ(1−σ′)^{2}T′} \binom{m_{1}m′}{T′}.  (251)

Recalling (238) and (239), we see that the quantity in (251) is

≤ (T′ + 1)^{m′−1}2^{m′−(T +T′)}β^{T +T′} \binom{m_{1}m′}{T′}.  (252)

We now recall that we are assuming that T̃ = T + T′ ≫ m′ log m′. Using (250), we deduce that T′ ≫ m′ log m′. Hence

(T′ + 1)^{m′−1}2^{−T′/2} ≪ 1.  (253)

Similarly,

2^{m′−T′/2} ≪ 1.  (254)

From (253) and (254), it follows that the quantity in (252) is

≤ β^{T +T′} \binom{m_{1}m′}{T′}.  (255)

The result now follows from (241) and (249), (251), (252), and (255). □

4.3.7. Proof of the one-sided neighbourhood lemma, r.gs version. The proof of Theorem 20 is based on Lemmas 8, 9, 18, and 19, and on Theorem 13.

Proof of Theorem 20. Let α, ε, σ, σ′, μ and ν be as in the statement of the theorem. We now invoke Lemma 19 with the following constants. We let β(19) = α/8e, ε(19) = ε, μ(19) = μ/2, ν(19) = ν, σ(19) = σ, σ′(19) = σ′, C_{∧}(19) = 20/α^{2}(1−σ)^{2}, and C_{ECB}(19) = 3/α. Then, Lemma 19 gives us positive constants β_{exc}(19), ε′(19), δ(19), η_{0}(19), and η_{1}(19).

We now invoke Lemma 18 with the following constants. We let β_{exc}(18) = β_{exc}(19), Q(18) = 20/α^{2}, σ(18) = σ, σ′(18) = σ′, η_{1}(18) = η_{1}(19), and C_{ECB}(18) = 3/α. Then Lemma 18 gives us constants ε′(18) and η_{0}(18).

We now let α(13) = α/4 and γ(13) = δ(19) and invoke Theorem 13, which gives us ε(13) > 0. Finally, we let δ(9) = η_{1}(18) = η_{1}(19) and let

ε′ = min \{\frac{1}{6}α, ε′(19), ε′(18), \frac{1}{4}ν, \frac{1}{6}αη_{0}(18), \frac{1}{6}αη_{0}(19), \frac{1}{2}νε(13), \frac{1}{5}ασ′, \frac{1}{4}νμ\} (256)

We claim that this choice for ε′ will do for Theorem 20. The remainder of this proof is dedicated to the proof of this claim.

We first give four almost sure properties of our random graph G = G(n, q). Lemma 8 tells us that we may assume that G = G(n, q) satisfies the following property.

(P_{1}) let m^{(1)} = m^{(1)}(n) be a function with qm^{(1)} ≫ log n. Then, if A and B are

two disjoint vertex sets with |A|, |B| ≥ m^{(1)}, we have e(G[A, B]) ∼ q|A||B|. Lemma 9 tells us that we may assume that the following property holds for G = G(n, q).

(P_{2}) let m^{(2)} = m^{(2)}(n) be a function with q^{2}m^{(2)} ≫ log n. Then, for any A, B ⊂ V (G) with A∩B = ∅ and |A|, |B| ≥ m^{(2)}, we have that for any F ⊂ \binom{A}{2}

with |F | ≤ δ(9)\binom{|A|}{2} = η_{1}(18)\binom{|A|}{2} we have
∑_{{x,y}∈F} d_{B}^{G}(x, y) ≤ 2δ(9)q^{2}|A|^{2}|B| = 2η_{1}(18)q^{2}|A|^{2}|B|.  (257)

By Theorem 13, we may assume that the following property holds in G = G(n, q).

(P_{3}) let m^{(3)} = m^{(3)}(n) be a function with q^{2}m^{(2)} ≫ (log n)^{4}. For any graph H ⊂ G such that e(H[A, B]) ≥ α(13)e(G[A, B]), if H[A, B] is (ε(13), q)-regular, then property PC(A, B; γ(13)) holds.

Finally, by Lemma 19, we may assume that the following holds for G = G(n, q).

(P_{4}) Let m^{(4)} = m^{(4)}(n) be such that qm^{(4)} ≫ log n. Consider pairs of bipartite graphs (B, B′) as in Lemma 19. Thus, we consider pairs (B, B′) for which the properties, notation and definitions given in (I), (II)(a) and (b), (III)(a′′) and (b), and (IV), and the compatibility conditions (184)–(186) in Sections 4.3.1 and 4.3.2 apply. Suppose further that m_{1} = |U| ≥ m^{(4)}, m_{2} + m′ = |W | + |W′| ≥ m^{(4)}, and that p = e(B)/|U||W | ≥ (α/2)q. Then, G contains no isomorphic copy of the pair (B, B′) as a subgraph.

Remark 30. We shall not give a proof for the fact that (P_{4}) does indeed hold almost surely for G = G(n, q). Such a proof, based on estimating the expected number of copies of such pairs (B, B′) in G = G(n, q) using Lemma 19, is similar to the proofs of Lemma 6 and Theorem 13 (see also Remark 26).

We now state and prove a deterministic statement that will complete the proof of Theorem 20.

Claim 24. If G satisfies properties (P_{1})–(P_{4}) above, then property

N (q, m_{0}; α, ε, σ, σ′, μ, ν; ε′)

holds.

Proof. To prove this claim, we assume that H = (U, W; F) ⊂ G is a bipartite subgraph of G and W = W′ ∪ W′′ is a partition of W for which conditions (1)–(3) in the definition of N (q, m_{0}; α, ε, σ, σ′, μ, ν; ε′) are satisfied. Our aim is to show that, then, for ≥ (1 − μ)m′_{2} vertices w′ ∈ W′, assertion (4) in that definition holds. For convenience, we state explicitly the hypotheses and the conclusion that we wish to derive. We are assuming that

(1) |U| = m_{1}, |W | = m_{2}, where m_{1}, m_{2} ≥ m_{0}, and |F | ≥ αe(G[U, W]),

(2) H = (U, W; F) is an ε′-regular bipartite graph with respect to density q,

(3) m′_{2} = |W′| ≥ νm_{2} and m′′_{2} = |W′′| ≥ νm_{2}. Then, putting p = e(H)/|U||W | = |F |/m_{1}m_{2} and H′ = H[U, W′] and H′′ = H[U, W′′], we wish to show that for ≥ (1 − μ)m′_{2} vertices w′ ∈ W′ the following assertion holds:

(4) if Ũ = Γ_{H′}(w′) and H(w′) = H′′[Ũ, W′′] = H[Ũ, W′′], then

(i) d_{H′}(w′) = |Ũ| ∼_{σ′} d_{1} = pm_{1},
(ii) ϱ(w′) = e(H(w′))/|Ũ||W′′| ∼_{σ} p,
(iii) H(w′) is (ε, ϱ(w′))-regular.

Let us prove (4).

Since |F | ≥ αe(G[U, W]) and property (P_{1}) holds, we have p = e(H)/|U||W | = |F |/m_{1}m_{2} ≳ αq. We assume from now on that

p ≥ \frac{1}{2}αq.  (258)

Let us now relate the densities p′ = e(H′)/|U||W′| and p′′ = e(H′′)/|U||W′′| of H′ and H′′ to that of H. From the (ε′, q)-regularity of H and the fact that ε′ ≤ ν (see (256)), we may deduce that

|\frac{e(U, W′)}{q|U||W′|} − \frac{e(U, W)}{q|U||W |}| = |\frac{p′}{q} − \frac{p}{q}| ≤ ε′.  (259)

Inequalities (259) and (258) gives that

|p′ − p| ≤ ε′q ≤ \frac{2ε′}{α} p,  (260)

that is, p′ ∼_{2ε′/α} p. A similar argument holds for p′′, and hence we have

p′ ∼_{2ε′/α} p  and  p′′ ∼_{2ε′/α} p.  (261)

The inequalities in (261) give that

p′ ∼_{5ε′/α} p′′.  (262)

Let us now check that conditions (I), (II)(a) and (b), (III)(a′′) and (b) hold for H′′ with the constants η_{0}(19), ε′(19), δ(19), σ′(19), η_{1}(19), C_{∧}(19), β_{exc}(19), and C_{ECB}(19). For clarity, we state these conditions explicitly.

(I) |U| = m_{1}, |W′′| = m′′_{2}, T′′ = e(H′′), p′′ = T′′/m_{1}m′′_{2}, d′′_{1} = p′′m_{1}, and d′′_{2} =

p′′m′′_{2}. (II) (a) Property D(U, W′′; η_{0}(19), ε′(19)) holds.

(b) Property PC(U, W′′; δ(19)) holds. (III) (a′′) For all d ∼_{σ′(19)} d′′_{1} = p′′m_{1}, we have

|E(d; η_{1}(19), C_{∧}(19))| ≤ β_{exc}(19)^{d}\binom{m_{1}}{d}.  (263)

Notice that E(d; η_{1}(19), C_{∧}(19)) is the family of sets U′ ⊂ U with |U′| = d for which property ChUB(U′, W′′; η_{1}(19), C_{∧}(19)) fails.

(b) Property ECB(U, W′′; C_{ECB}(19)) holds. In particular, if Ū ⊂ U is such that |Ū| ≥ d′′/(log m′′)^{3}, then

e(Ū, W) ≤ C_{ECB}(19)p′′|Ū||W′′|,  (264)

where d′′ = min{d′′_{1}, d′′_{2}} and m′′ = m′′_{+} = max{m_{1}, m′′_{2}}.

We now verify the assertions above one by one. (I) |U| = m_{1}, |W′′| = m′′_{2}, T′′ = e(H′′), p′′ = T′′/m_{1}m′′_{2}, d′′_{1} = p′′m_{1}, and d′′_{2} = p′′m′′_{2}. Assertion (I) only introduces some notation, so there is nothing to verify.

(II)(a) Property D(U, W′′; η_{0}(19), ε′(19)) holds. Let U′ ⊂ U be such that |U′| ≥ ε′(19)|U|. From the fact that ε′ ≤ ε′(19) and ε′ ≤ ν (see (256)), and the fact that we are assuming that H is (ε′, q)-regular (see assumption (2)), we have

|\frac{e(U′, W′′)}{q|U′||W′′|} − \frac{e(U, W)}{q|U||W |}| ≤ ε′  (265)

and

|\frac{e(U, W′′)}{q|U||W′′|} − \frac{e(U, W)}{q|U||W |}| ≤ ε′.  (266)

Therefore, recalling that p′′/q = e(U, W′′)/q|U||W′′|, we have from (265) and (266) that

|\frac{e(U′, W′′)}{q|U′||W′′|} − \frac{p′′}{q} | ≤ 2ε′.  (267)

Inequality (267) implies that

|e(U′, W′′) − p′′|U′||W′′|| ≤ 2ε′q|U′||W′′| ≤ \frac{4}{α}ε′p|U′||W′′|

≤ \frac{4}{α}ε′ \frac{p′′}{1 − 2ε′/α}|U′||W′′| ≤ η_{0}(19)p′′|U′||W′′|, (268)

where we used inequalities (258), (261), and (256).

(II)(b) Property PC(U, W′′; δ(19)) holds. We start by observing that |U|, |W′′| ≫ q^{2}(log n)^{4} and hence property (P_{3}) above applies to these sets. We have, by (P_{1}), (258), and (261),

e(U, W′′) = p′′|U||W′′| ∼ \frac{p′′}{q} e(G[U, W′′])

≥ (1 − \frac{2ε′}{α} ) \frac{p}{q}e(G[U, W′′]) ≥ (1 − \frac{2ε′}{α} ) \frac{α}{2}e(G[U, W′′]). (269)

Using that ε′ ≤ α/6 (see (256)), we have that

e(U, W′′) ≳ \frac{1}{3}αe(G[U, W′′]).  (270)

Recalling that α(13) = α/4, we may conclude from (270) that

e(U, W′′) ≥ α(13)e(G[U, W′′]).  (271)

Since H[U, W] is (ε′, q)-regular and |W′′| ≥ ν|W |, we know that H[U, W′′] is (2ε′/ν, q)-regular. Since ε′ ≤ νε(13)/2, we deduce that H[U, W′′] is (ε(13), q)- regular. We may then apply (P_{3}) to conclude that property PC(U, W′′; γ(13)) = PC(U, W′′; δ(19)) holds.

It will be convenient to prove (III)(b) before (III)(a′′). (III)(b) Property ECB(U, W′′; C_{ECB}(19)) holds. Recall (258) and (261), and observe that we therefore have

p′′ ≥ \frac{1}{2} (1 − \frac{2ε′}{α} ) αq.  (272)

Since m_{1} ≥ m_{0} and m′′_{2} ≥ νm_{2} ≥ νm_{0} (recall assumptions (1) and (3)), we have from (272) that

d′′ = min\{d′′_{1}, d′′_{2}\} = min\{p′′m_{1}, p′′m′′_{2}\} ≥ \frac{1}{2} (1 − \frac{2ε′}{α} ) ανqm_{0}.  (273)

Put m′′ = m′′_{+} = max{m_{1}, m′′_{2}}, and observe that

q × \frac{d′′}{(log m′′)^{3}} ≥ \frac{1}{2} (1 − \frac{2ε′}{α} ) αν \frac{q^{2}m_{0}}{(log n)^{3}} ≫ log n,  (274)

where for the last inequality we used the second inequality in (190). Hence property (P_{1}) tells us that, for any two disjoint sets A and B with |A|, |B| ≥ d′′/(log m′′)^{3}, we have

e(H[A, B]) ≤ e(G[A, B]) ∼ q|A||B| ≤ \frac{2}{α}p|A||B|,  (275)

where we again used (258). However, since C_{ECB}(19) = 3/α, we have from (275) that

e(H[A, B]) ≤ C_{ECB}(19)p|A||B|.  (276)

Therefore ECB(U, W′′; C_{ECB}(19)) does hold.

(III)(a′′) For all d ∼_{σ′(19)} d′′_{1} = p′′m_{1}, we have

|E(d; η_{1}(19), C_{∧}(19))| ≤ β_{exc}(19)^{d}\binom{m_{1}}{d}.  (277)

Recall that E(d; η_{1}(19), C_{∧}(19)) is the family of sets U′ ⊂ U with |U′| = d for which property ChUB(U′, W′′; η_{1}(19), C_{∧}(19)) fails.

We shall use Lemma 18. Note that hypotheses (I), (II)(a), and (III)(b) of that lemma have already been verified for H′′. We now check condition (III)(a′) for H′′, making use of (P_{2}). Let U′ ⊂ U with d = |U′| ∼_{σ′(18)} d′′_{1} be fixed. Using the first inequality in (190), (258), and (261), we have

|U′| ∼_{σ′(18)} d′′_{1} = p′′m_{1} ∼_{2ε′/α} pm_{1} ≥ \frac{1}{2}αqm_{1} ≥ \frac{1}{2}αqm_{0} ≫ q^{−2} log n. (278)

We also have |W′′| ≫ q^{−2} log n with lots of room to spare, since

|W′′| ≥ ν|W | = νm_{2} ≥ νm_{0} ≫ q^{−3} log n.  (279)

Property (P_{2}) with A = U′ and B = W′′ tells us that for any F ⊂ \binom{U′}{2} with |F | ≤ δ(9)\binom{|U′|}{2} = η_{1}(18)\binom{|U′|}{2} we have

∑_{{x,y}∈F} d_{B}^{G}(x, y) ≤ 2δ(9)q^{2}|U′|^{2}|W′′| = 2η_{1}(18)q^{2}|U′|^{2}|W′′|.  (280)

The right-hand side of (280) is, by (258) and (261),

≤ 2η_{1}(18) (\frac{2p}{α})^{2} |U′|^{2}|W′′| ≤ \frac{8}{α^{2}} (\frac{1}{1 − 2ε′/α})^{2} η_{1}(18)(p′′)^{2}|U′|^{2}|W′′|

≤ Q(18)η_{1}(18)(p′′)^{2}|U′|^{2}|W′′|. (281)

Lemma 18 then implies that (277) holds for all d ∼_{σ′(19)} d′′_{1} = p′′m_{1}. Here we use that Lemma 18 was invoked with the ‘right’ constants, namely, σ′(18) = σ′(19) = σ′, β_{exc}(18) = β_{exc}(19), η_{1}(18) = η_{1}(19), and C_{∧}(19) = Q(18)/(1−σ)^{2} = 20/α^{2}(1− σ)^{2}.

We have thus checked that conditions (I), (II)(a) and (b), (III)(a′′) and (b) hold for H′′. We now consider the ‘compatibility’ conditions (184)–(186) for H′ = (U, W′; F′) with respect to H′′ = (U, W′′; F′′). Again for clarity, we state these compatibility conditions explicitly.

The first condition states that

m′_{2} ≥ ν(|W′| + |W′′|) = ν(m′_{2} + m′′_{2}) = νm_{2}.  (282)

The second conditions is that

p′ = \frac{e(H′)}{m_{1}m′_{2}} ∼_{σ′(19)} p′′ = \frac{e(H′′)}{m_{1}m′′_{2}} .  (283)

The last condition is that

for at least m′_{2}/2 vertices w′ ∈ W′_{2}, we have

d_{H′}(w′) = |Γ_{H′}(w′)| ∼_{σ′(19)} d′′_{1} = p′′m_{1}. (284)

(*) The compatibility conditions (282)–(284) for H′ = (U, W′; F′) with respect to H′′ = (U, W′′; F′′) do hold. We have as an assumption that |W′| = m′_{2} ≥ ν|W | = νm_{2}, and hence (282) is satisfied. Let us now consider (283). Since σ′(19) ≥ 5ε′/α (see (256)), relation (262) tells us that (283) holds. We now verify (284).

Observe that the (ε′, q)-regularity of H implies that for ≥ (1 − 2ε′)m_{2} vertices w ∈ W we have, by (258),

|d_{H}(w) − pm_{1}| ≤ ε′qm_{1} ≤ ε′ (\frac{2p}{α}) m_{1}.  (285)

Inequality (285) is equivalent to d_{H}(w) ∼_{2ε′/α} pm_{1}. This, coupled with (261), implies that

for at least (1 − 2ε′/ν)m′_{2} vertices w′ ∈ W′,

we have d_{H′}(w′) ∼_{5ε′/α} d′′_{1} = p′′m_{1}. (286)

Since σ′(19) ≥ 5ε′/α and 2ε′/ν ≤ 1/2 (see (256)), the condition in (284) holds. We have thus checked that H′ is compatible with H′′.

We are now approaching the end of the proof of Claim 24. It is worth recalling that our aim is to prove assertions (i), (ii), and (iii) of (4) in the definition of property N (q, m_{0}; α, ε, σ, σ′, μ, ν; ε′), reproduced at the beginning of the proof of this claim.

We have already observed that the (ε′, q)-regularity of H implies that, for ≥ (1 − 2ε′)m_{2} vertices w ∈ W, we have d_{H}(w) ∼_{2ε′/α} d_{1} = pm_{1}. But then, in view of the fact that 2ε′/ν ≤ μ/2 (see (256)) and 2ε′/α ≤ σ′ (see (256)), this implies that for ≥ (1 − μ/2)m′_{2} vertices w′ ∈ W′ we have that (4)(i) holds. We now consider properties (4)(ii) and (4)(iii). We invoke property (P_{4}).

Since we know that the pair of compatible graphs (H′′, H′) satisfies conditions (I), (II)(a) and (b), (III)(a′′) and (b), and we are assuming, according to (P_{4}), that G contains no pair (B, B′) satisfying all these conditions and condition (IV), we deduce that condition (IV) must fail for (H′′, H′). In other words, the number of (ε(19), σ(19), σ′(19); H′′, H′)-bad vertices is less than μ(19)m′_{2} = (μ/2)m′_{2}. Hence, for ≥ (1 − μ/2)m′_{2} vertices w′ ∈ W′, putting Ũ = Ũ(w′) = Γ_{H′′}(w′), we have that

(a) ϱ_{w′} = e(H′′[Ũ, W])/|Ũ||W | ∼_{σ(19)} p = T/m_{1}m_{2} holds,

(b) H′′[Ũ, W] is (ε(19), ϱ_{w′})-regular, and

(c) Ũ ∈ E(|Ũ|; η_{1}(19), C_{∧}(19)). Now recall that σ(19) = σ and ε(19) = ε, and note that (a) above corresponds to (4)(ii) and that (b) above corresponds to (4)(iii).

We conclude that for ≥ (1 − μ)m′_{2} vertices w′ ∈ W′ we have that properties (i), (ii), and (iii) of (4) in the definition of property N (q, m_{0}; α, ε, σ, σ′, μ, ν; ε′) hold (see Definition 27). This finishes the proof of Claim 24. □

The proof of Theorem 20 is complete. □

4.4. The k-tuple lemma for subgraphs of random graphs. Theorems 13, 16, and 20, i.e., the pair condition lemma, the the local condition lemma, and the onesided neighbourhood lemma (all of these in the r.gs version) imply a generalization of Theorem 13. This generalization is Theorem 25 below.

Let us remark in passing that we do not give a generalization of Lemma 12 that extends this lemma in the same direction that Theorem 25 extends Theorem 13; such a generalization would be a result concerning the number certain ‘exceptional’ ε-regular bipartite graphs. The reason we omit this ‘counting version’ of Theorem 25 is that it would be quite technical. Instead, we prove directly the random graphs result that is relevant in applications.

Roughly speaking, in this section, we aim at estimating the number of k-tuples of vertices that have joint neighbourhoods of the wrong size in sparse ε-regular bipartite graphs that arise as subgraphs of random graphs.

4.4.1. The statement of the k-tuple lemma. Let G = G(n, q) be the binomial random graph with edge probability q = q(n), and suppose H = (U, W; F) is a bipartite subgraph of G. Consider the following three assertions for H.

(I) |U| = m_{1}, |W | = m_{2}, d_{i} = pm_{i} (i ∈ {1, 2}), p = e(H)/m_{1}m_{2}, and e(H) ≥

αe(G[U, W]). (II) H[U, W] is (ε, q)-regular. (III) We have m_{0} = m_{0}(n) such that

q^{k}m_{0} ≫ (log n)^{4},  (287)

and

m_{1}, m_{2} ≥ m_{0}.  (288)

We now consider subsets R ⊂ W of some fixed cardinality, say k, with k ≥ 2, and classify them according to the size of their joint neighbourhood in H. In fact, we let

B^{(k)}(U, W; γ) = B_{H}^{(k)}(U, W; γ) = \{R ∈ \binom{W}{k}: |d_{U}^{H}(R) − p^{k}m_{1}| ≥ γp^{k}m_{1}\} ,

(289)

where

d_{U}^{H}(R) = |U ∩ ⋂_{x∈R} Γ_{H}(x)| = | ⋂_{x∈R} Γ_{H}(x)| .  (290)

Note that, in particular, B^{(2)}(U, W; γ) = F_{H}(W, U; γ). We are interested in an upper estimate for |B^{(k)}(U, W; γ)|. Consider the inequality

(IV)

|B^{(k)}(U, W; γ)| ≤ η\binom{m_{2}}{k}.  (291)

Our result states that property (IV) may be guaranteed almost surely for arbitrarily small constants γ > 0 and η > 0, by requiring that the graph H = (U, W; F) should be ε-regular with a suitably small ε.

Theorem 25 (The k-tuple lemma, r.gs version). For all α > 0, γ > 0, η > 0, and k ≥ 2, there is ε > 0 such that almost every G = G(n, q) satisfies the following property. If conditions (I)–(III) apply to a bipartite subgraph H = (U, W; F) of G then condition (IV) also applies.

4.4.2. The proof of the k-tuple lemma. In this section, we prove the k-tuple lemma for subgraphs of random graphs, Theorem 25.

Proof of Theorem 25. The proof will be by induction on k. To formalise the proof, we start by making the following definition.

Definition 31 (Π_{k}(α, γ, η, k; ε)). We say that property Π_{k}(α, γ, η, k; ε) holds for a graph G if any subgraph H = (U, W; F) of G that satisfies properties (I)–(III) with parameters α, ε, and k also satisfies property (IV) with parameters γ, η, and k.

We shall prove by induction on k that the following statement holds for all k ≥ 2. (S_{k}) for every α > 0, γ > 0, and η > 0, there is ε > 0 such that

ℙ{Π_{k}(α, γ, η, k; ε) holds for G(n, q)} = 1 − o(1).  (292)

Suppose k = 2. Apply Theorem 13 with constants α(13) = α and γ(13) = min{γ, η}. Theorem 13 then gives a constant ε(13) > 0. It then suffices to take ε = ε(13). Relation (292) then follows from Theorem 13.

We now proceed to the induction step. Assume that k ≥ 3 and that (S_{k−1}) holds. Let α = α_{k} > 0, γ = γ_{k} > 0 and η = η_{k} > 0 be given. In order to define an appropriate constant ε = ε_{k} > 0 to make (292) hold, we invoke the induction hypothesis (S_{k−1}) and Theorem 20.

We need some technical preparation. Let γ_{0}, σ_{0}, and σ′_{0} be small enough positive constants satisfying the following properties:

0 < σ_{0} ≤ \frac{1}{k − 1}  and  0 < σ′_{0} ≤ 1,  (293)

(1 + γ_{0})(1 + 2{2(k − 1)σ_{0} + σ′_{0}}) ≤ 1 + γ,  (294)

and

(1 − γ_{0})(1 − 2{2(k − 1)σ_{0} + σ′_{0}}) ≥ 1 − γ.  (295)

Below, we shall use that, for any integer ℓ ≥ 1,

(1 + x)^{ℓ} ≤ 1 + 2ℓx for all 0 ≤ x ≤ 1/ℓ,  (296)

and

(1 − x)^{ℓ} ≥ 1 − ℓx for all 0 ≤ x ≤ 3/ℓ.  (297)

Moreover,

(1 + x)(1 + y) ≤ 1 + 2(x + y) if x, y ≥ 0 and min{x, y} ≤ 1,  (298)

and

(1 − x)(1 − y) ≥ 1 − x − y if x, y ≥ 0.  (299)

We now let α_{k−1} = α/3, γ_{k−1} = γ_{0}, and η_{k−1} = η/10 and invoke the induction hypothesis (S_{k−1}) with these constants. Then, assertion (S_{k−1}) gives us a constant ε_{k−1} > 0. We now apply Theorem 20 with the following constants: let α(20) = α, ε(20) = ε_{k−1}/4, σ(20) = σ_{0}, σ′(20) = σ′_{0}, μ(20) = η/10, and ν(20) = 1/k. Then, Theorem 20 gives us a constant ε′(20) > 0. We put

ε = ε_{k} = ε′(20),  (300)

and claim that (292) holds with this choice of ε.

To prove our claim, let us consider G = G(n, q). Because of the choice of ε_{k−1}, almost surely

property Π_{k−1}(α_{k−1}, γ_{k−1}, η_{k−1}, k − 1; ε_{k−1}) holds for G.  (301)

Recall now the definition of property N (q, m_{0}; α, ε, σ, σ′, μ, ν; ε′) (see Definition 27). Recall also that q^{3}m_{0} ≥ q^{k}m_{0} ≫ (log n)^{4} ≥ log n (see (287) in (III)). By the choice of ε = ε′(20) (see Theorem 20), we almost surely have that

property N (q, m_{0}; α, ε_{k−1}/4, σ_{0}, σ′_{0}, η/10, 1/k; ε) holds for G.  (302)

Moreover, by Lemma 8, almost surely the following property holds for G = G(n, q).

(*) let m^{(1)} = m^{(1)}(n) be a function with qm^{(1)} ≫ log n. Then, if A and B are two disjoint vertex sets with |A|, |B| ≥ m^{(1)}, we have e(G[A, B]) ∼ q|A||B|.

We now state the following claim.

Claim 26. Suppose (301), (302), and (*) hold. Then

property Π_{k}(α, γ, η, k; ε) holds for G.  (303)

Since (301), (302), and (*) hold with probability 1 − o(1), Claim 26 implies that (292) holds, and hence the induction step will be complete once we prove this claim.

The proof of Claim 26 will be by contradiction, and it will be mostly based on four subclaims (a)–(d).

Proof of Claim 26. To verify (303), let H = (U, W; F) ⊂ G be such that (I)–(III) hold with parameters α, ε, and k. We have to verify (291). Put B = B_{H}^{(k)}(U, W; γ), and suppose for a contradiction that

|B| > η\binom{m_{2}}{k}.  (304)

A standard averaging argument gives the following. There is a partition W = W′ ∪ W′′ with m′_{2} = |W′| = m_{2}/k and m′′_{2} = |W′′| = (1 − 1/k)m_{2} such that

B′ = {R ∈ B: |R ∩ W′| = 1}  (305)

satisfies

|B′| ≥ \frac{1}{2}c_{k}|B| ≥ \frac{1}{2}ηc_{k}\binom{m_{2}}{k},  (306)

where c_{k} = (1 − 1/k)^{k−1}. Fix such a partition W = W′ ∪ W′′. Following the notation of Theorem 20, we let H′ = H[U, W′] and H′′ = H[U, W′′].

In what follows,

d_{B′}(w′) = |{R ∈ B′: w′ ∈ R}|  (307)

is the degree of w′ in the set system or hypergraph B′. We claim that assertion (a) below holds. Note that this claim concerns the existence of many vertices w′ ∈ W′ that belong to many k-tuples R ∈ B′.

(a) At least (η/6)m′_{2} = (η/6)|W′| vertices w′ ∈ W′ are such that

d_{B′}(w′) ≥ \frac{η}{6} \binom{m′′_{2}}{k − 1}.  (308)

To verify assertion (a), note that otherwise we would have

|B′| = ∑_{w′∈W′} d_{B′}(w′) < \frac{η}{6} m′_{2} × \binom{m′′_{2}}{k − 1} + m′_{2} × \frac{η}{6} \binom{m′′_{2}}{k − 1}

= \frac{η}{3} m′_{2}\binom{m′′_{2}}{k − 1} ∼ \frac{η}{3} \frac{m_{2}}{k} (1 − \frac{1}{k} )^{k−1} \binom{m_{2} − 1}{k − 1} = \frac{1}{3}ηc_{k}\binom{m_{2}}{k},

which contradicts (306). Hence (a) does hold.

We now come to an assertion concerning vertices that behave well with respect to the graph H.

(b) There are at least (1 − η/10)m′_{2} = (1 − η/10)|W′| vertices w′ ∈ W′ such that if Ũ = Γ_{H′}(w′) and H̃ = H[Ũ, W′′], then

(i) d_{H′}(w′) = |Ũ| ∼_{σ′_{0}} d_{1} = pm_{1}, (ii) ϱ(w′) = e(H̃)/|Ũ||W′′| ∼_{σ_{0}} p, (iii) H̃ is (ε_{k−1}/4, ϱ(w′))-regular.

To prove (b), first recall that (302) holds. To apply property

N (q, m_{0}; α, ε_{k−1}/4, σ_{0}, σ′_{0}, η/10, 1/k; ε),

consider H = (U, W; F) ⊂ G and the partition W = W′ ∪ W′′ defined above. By hypothesis (I), we have that e(H[U, W]) ≥ αe(G[U, W]) holds. By (II), we know that H[U, W] is (ε, q)-regular. By (III), we have m_{1}, m_{2} ≥ m_{0}. Finally, we recall that |W′| ≥ ν(20)|W | = (1/k)|W | and |W′′| = (1 − 1/k)|W | ≥ ν(20)|W | = (1/k)|W |. Therefore we may apply property N (q, m_{0}; α, ε_{k−1}/4, σ_{0}, σ′_{0}, η/10, 1/k; ε), to deduce that there exist at least (1−μ(20))|W′| = (1−η/10)|W′| vertices w′ ∈ W′ for which (i)–(iii) above hold. This completes the proof of (b).

From assertions (a) and (b) above, we know that there are at least (η/6 − η/10)|W′| = (η/15)|W′| vertices w′ ∈ W′ for which inequality (308) and properties (i)–(iii) in assertion (b) hold. We now fix one such vertex w′ and consider Ũ = Γ_{H′}(w′), H̃ = H[Ũ, W′′], and ϱ(w′) = e(H̃)/|Ũ||W′′|.

Consider

B̃ = B̃(w′) = B(k−1) ; H̃(Ũ, W′′; γ_{k−1})
= \{R̃ ∈ \binom{W′′}{k − 1}: |dH̃ ; Ũ(R̃) − ϱ^{k−1}|Ũ|| ≥ γ_{k−1}ϱ^{k−1}|Ũ|\} ,  (309)

where ϱ = ϱ(w′) ∼_{σ_{0}} p and

dH̃ ; Ũ(R̃) = |Ũ ∩ ⋂_{x∈R̃} ΓH̃(x)| = | ⋂_{x∈R̃} ΓH̃(x)| .  (310)

Our next claim is as follows.

(c) We have

|B̃| = |B̃(w′)| ≥ \frac{η}{6} \binom{m′′_{2}}{k − 1}.  (311)

To prove assertion (c), we observe that if (308) holds, then (311) must also hold. More precisely, we have that if R = R̃∪{w′} ∈ B′ holds, where R̃ ⊂ W′′, then R̃ ∈ B̃ must hold. Let us check this last implication. Suppose R = R̃ ∪ {w′} ∈ B′, where R̃ ⊂ W′′. Then

|d_{U}^{H}(R) − p^{k}m_{1}| ≥ γp^{k}m_{1}.  (312)

In order to show that R̃ ∈ B̃, we need to show that

|dH̃ ; Ũ(R̃) − ϱ^{k−1}|Ũ|| ≥ γ_{k−1}ϱ^{k−1}|Ũ|.  (313)

Observe that (ii) of claim (b) and (296) and (297) with ℓ = k − 1 and (293) imply that

ϱ^{k−1}|Ũ| ∼_{2(k−1)σ_{0}} p^{k−1}|Ũ|.  (314)

The right-hand side of (314) is, by (i) of claim (b),

∼_{σ′_{0}} p^{k}m_{1}.  (315)

Relations (314) and (315) imply, by (293), (298) and (299), that

ϱ^{k−1}|Ũ| ∼_{2{2(k−1)σ_{0}+σ′_{0}}} p^{k}m_{1}.  (316)

Thus, recalling that γ_{k−1} = γ_{0}, we have, by (294) and (295), that

(1 − γ)p^{k}m_{1} ≤ (1 − γ_{k−1})(1 − 2{2(k − 1)σ_{0} + σ′_{0}})p^{k}m_{1}

≤ (1 − γ_{k−1})ϱ^{k−1}|Ũ| ≤ (1 + γ_{k−1})ϱ^{k−1}|Ũ|

≤ (1 + γ_{k−1})(1 + 2{2(k − 1)σ_{0} + σ′_{0}})p^{k}m_{1} ≤ (1 + γ)p^{k}m_{1}. (317)

However, the string of inequalities in (317) implies that, indeed, inequality (312) implies inequality (313). Thus assertion (c) is proved.

We now recall that (301) holds, and apply this to H̃ = H[Ũ, W′′] ⊂ G. In order to do this, we have to verify that conditions (I)–(III) apply to H̃.

(d) Properties (I)–(III) hold for H̃ = H[Ũ, W′′] with parameters α_{k−1} = α/3, ε_{k−1}, and k − 1. Using hypothesis (I) on H and (*), we observe that e(H[U, W]) ≥ αe(G[U, W]) ∼ αq|U||W |, and hence p = e(H[U, W])/|U||W | ≳ αq. To verify (I) for H̃ = H[Ũ, W′′], we use (*) again to deduce that e(G[Ũ, W′′]) ∼ q|Ũ||W′′|, and hence, by (b)(ii), we have ϱ = ϱ(w′) ∼_{σ_{0}} p ≳ αq. Since α_{k−1} = α/3, we obtain that e(H[Ũ, W′′]) ≥ α_{k−1}e(G[Ũ, W′′]) and assertion (I) follows for H̃ with parameter α_{k−1} = α/3.

For later reference, let us observe that (*) also implies that

p = \frac{e(H[U, W])}{|U||W |} ≤ \frac{e(G[U, W])}{|U||W |} ∼ q,  (318)

and hence we may assume that p ≤ 2q.

We turn to (II). Our choice of w′ guarantees that H̃ = H[Ũ, W′′] is (ε_{k−1}/4, ϱ)- regular (see (b)(iii)). To verify (II), we shall show that this implies that H̃ is (ε_{k−1}, q)-regular. Suppose Ũ′ ⊂ Ũ and W′′′ ⊂ W′′ are such that |Ũ′| ≥ ε_{k−1}|Ũ| and |W′′′| ≥ ε_{k−1}|W′′|. By the (ε_{k−1}/4, ϱ)-regularity of H̃ = H[Ũ, W′′], and recalling that

ϱ = \frac{e(H̃)}{|Ũ||W′′|} = \frac{e(H[Ũ, W′′])}{|Ũ||W′′|},  (319)

we see that

|\frac{e(H[Ũ′, W′′′])}{ϱ|Ũ′||W′′′|} − \frac{e(H[Ũ, W′′])}{ϱ|Ũ||W′′|}| = |\frac{e(H[Ũ′, W′′′])}{ϱ|Ũ′||W′′′|} − 1| ≤ \frac{1}{4}ε_{k−1}.  (320)

But then, we have

|\frac{e(H[Ũ′, W′′′])}{q|Ũ′||W′′′|} − \frac{e(H[Ũ, W′′])}{q|Ũ||W′′|}| = |\frac{e(H[Ũ′, W′′′])}{q|Ũ′||W′′′|} − \frac{ϱ}{q}|

= \frac{ϱ}{q} |\frac{e(H[Ũ′, W′′′])}{ϱ|Ũ′||W′′′|} − 1| ≤ \frac{ϱ}{4q} ε_{k−1}

≤ \frac{ϱ}{2p}ε_{k−1} ≤ \frac{1}{2}(1 + σ_{0})ε_{k−1} ≤ ε_{k−1}, (321)

where we used that, as observed above, q ≥ p/2 and ϱ ∼_{σ_{0}} p (cf. (b)(ii)). It now suffices to notice that (321) implies that H̃ = H[Ũ, W′′] is indeed (ε_{k−1}, q)-regular.

Finally, for (III), we observe that, by (b)(i) and the fact that p ≳ αq,

q^{k−1}|Ũ| ∼_{σ′_{0}} q^{k−1}pm_{1} ≳ αq^{k}m_{1} ≫ (log n)^{4}.  (322)

Moreover,

q^{k−1}|W′′| = q^{k−1} (1 − \frac{1}{k} ) |W | = (1 − \frac{1}{k} ) q^{k−1}m_{2} ≫ (log n)^{4}.  (323)

Therefore we indeed do have that properties (I)–(III) hold for H̃ = H[Ũ, W′′]. Since (301) holds and assertion (d) above holds, we conclude that

|B̃| = |B(k−1) ; H̃(Ũ, W′′; γ_{k−1})| ≤ η_{k−1}\binom{m′′_{2}}{k − 1} = \frac{η}{10}\binom{m′′_{2}}{k − 1}.  (324)

Comparing (311) and (324), we arrive at a contradiction. Therefore (304) must fail and hence (303) does hold. This completes the proof of Claim 26. □

As observed after the statement of Claim 26, the validity of this claim completes the induction step and hence Theorem 25 follows by induction. □

5. An example

In Section 4.1, we remarked that, in the sparse context, the o(1)-regularity of a bipartite graph B = (U, W; E) does not necessarily imply property PC(U, W; o(1)) (cf. Remark 17). In this section we justify this claim.

5.1. The construction. We shall prove the existence of examples of bipartite graphs (U, W; E) that are very regular, but fail to satisfy property PC(U, W; γ) for some fixed γ > 0. Clearly, our graphs will have vanishing density, since we know that o(1)-regularity implies PC(U, W; o(1)) in the ‘dense’ set-up. The proof will be probabilistic.

Theorem 27. For every 0 < α < 1 and 0 < ε < 1, there exist 0 < p < 1 and m_{0} ≥ 1 such that for every m > m_{0} there is a bipartite graph J = (U, W; E) with |U| = |W | = m and |E| ∼_{ε} pm^{2} such that

(i) J satisfies the following property: for all U′ ⊂ U and W′ ⊂ W with |U′|, |W′| ≥ εm, we have

||E[U′, W′]| − p|U′||W′|| ≤ εp|U′||W′|,  (325)

while (ii) for all but ≤ αm^{2} pairs \{u_{1}, u_{2}\} ∈ \binom{U}{2}, we have

Γ_{J}(u_{1}) ∩ Γ_{J}(u_{2}) = ∅ and consequently ||Γ_{J}(u_{1}) ∩ Γ_{J}(u_{2})| − p^{2}m| > εp^{2}m. (326)

The proof of Theorem 27 will be based on the two claims below.

Claim 28. Let T = (A, B; F) be a bipartite graph and let a function μ: A ∪ B → [0, 1] be given. Assume moreover that

both μ(A) = ∑_{a∈A} μ(a) and μ(B) = ∑_{b∈B} μ(b) are integers.  (327)

Then there exist sets A_{i} ⊂ A and B_{i} ⊂ B (i ∈ {0, 1}) such that (i) |A_{0}| = |A_{1}| = ∑_{a∈A} μ(a), (ii) |B_{0}| = |B_{1}| = ∑_{b∈B} μ(b),

and

(iii)

|F [A_{0}, B_{0}]| ≤ ∑_{ab∈F} μ(a)μ(b) ≤ |F [A_{1}, B_{1}]|,  (328)

where

|F [A_{i}, B_{i}]| = e(T [A_{i}, B_{i}]) = |{(a, b): a ∈ A_{i}, b ∈ B_{i}, ab ∈ F }|.  (329)

Proof. Set M(A) = {a ∈ A: 0 < μ(a) < 1} and M(B) = {b ∈ B: 0 < μ(b) < 1}. We shall prove the existence of the sets A_{0} and B_{0}; the sets A_{1} and B_{1} may be constructed analogously.

Assume that M(A) ≠ ∅ or M(B) ≠ ∅. We shall alter μ in two rounds, maintaining valid the following assertions:

(a) properties (i) and (ii) hold,

(b) M(A) = ∅ after the first round, and M(A) ∪ M(B) = ∅ after the second

round, and, moreover,

(c) the value of ∑_{ab∈F} μ(a)μ(b) decreases in each round. (For constructing A_{1} and B_{1}, we would proceed analogously—maintaining (a) and (b), while increasing the value of the sum in (c).) Without loss of generality, assume that M(A) = {a_{1}, …, a_{r}} ≠ ∅. Assume that

μ(Γ_{T} (a_{1})) ≤ ⋯ ≤ μ(Γ_{T} (a_{r})).  (330)

Since μ(A) is an integer (see (327)),

r̄ = ∑_{i=1}^{r} μ(a_{i})  (331)

must be an integer as well. We define μ_{A}: A ∪ B → [0, 1] as follows:

μ_{A}(a_{1}) = ⋯ = μ_{A}(ar̄) = 1,  μ_{A}(a_{r̄+1}) = ⋯ = μ_{A}(a_{r}) = 0,  (332)

and

μ_{A}(x) = μ(x) for all x ∈ (A ∪ B) \ {a_{1}, …, a_{r}}.  (333)

Observe that μ_{A} satisfies property (a), we have M(A) = ∅, and

∑_{ab∈F} μ_{A}(a)μ_{A}(b) ≤ ∑_{ab∈F} μ(a)μ(b).  (334)

Now, if M(B) = ∅, then, putting,

A_{0} = {a ∈ A: μ_{A}(a) = 1} and B_{0} = {b ∈ B: μ_{A}(b) = 1},  (335)

we have that (i), (ii), and (iii) hold and we are done. Therefore, let us assume that M(B) ≠ ∅. We repeat the procedure of the first round with A replaced by B. More precisely, if M(B) = {b_{1}, …, b_{s}} ≠ ∅,

μ(Γ_{T} (b_{1})) ≤ ⋯ ≤ μ(Γ_{T} (b_{s})),  (336)

and s̄ = ∑_{i=1}^{s} μ(b_{i}), we define μ_{B}: A ∪ B → [0, 1] as follows:

μ_{B}(b_{1}) = ⋯ = μ_{B}(bs̄) = 1,  μ_{B}(b_{s̄+1}) = ⋯ = μ_{B}(b_{s}) = 0,  (337)

and

μ_{B}(x) = μ_{A}(x) for all x ∈ (A ∪ B) \ {b_{1}, …, b_{s}}.  (338)

Set

A_{0} = {a ∈ A: μ_{B}(a) = 1} and B_{0} = {b ∈ B: μ_{B}(b) = 1},  (339)

and observe that (i), (ii), and (iii) hold. □

The second claim on which the proof of Theorem 27 is based is as follows.

Claim 29. For every 0 < α < 1/2 and 0 < ε < 1/2, there exist an integer t and a bipartite graph T = (A, B; F) with |A| = |B| = t and satisfying the following properties.

(i) |F | = dt^{2}, where

d ∼_{ε} \frac{α}{\sqrt{t}},  (340)

(ii) For every A′ ⊂ A and B′ ⊂ B with |A′| ≥ ε|A| and |B′| ≥ ε|B|, we have

|F [A′, B′]| = e(T [A′, B′]) ∼_{ε} \frac{α}{\sqrt{t}}|A′||B′|,  (341)

where the notation is as in (329), and (iii)

|\{\{a, a′\} ∈ \binom{A}{2}: Γ_{T} (a) ∩ Γ_{T} (a′) = ∅\}| ≥ (1 − α)\binom{t}{2}.  (342)

Proof. Let t be such that

\sqrt{t} ≥ \frac{3 log 8}{ε^{4}α},  (343)

and consider the binomial random bipartite graph 𝕋 = (A, B; 𝔽), where each edge is chosen independently with probability p = α/\sqrt{t}. We shall use the following form of Chernoff’s inequality: let 𝔽_{n,p} be a random variable with binomial distribution Bi(n, p); then, for all 0 < ε < 1,

ℙ(|𝔽_{n,p} − np| > εnp) < exp \{−\frac{1}{3}ε^{2}np\} .  (344)

Fix A′ ⊂ A and B′ ⊂ B, with |A′| = a′ ≥ εt and |B′| = b′ ≥ εt. We use (344) to infer that

ℙ (|𝔽[A′, B′] − pa′b′| > εpa′b′) < exp \{−\frac{1}{3}ε^{2}pa′b′\} ≤ exp \{−\frac{1}{3}ε^{4}αt^{3/2}\} . (345)

On the other hand, the number of choices for A′ and B′ does not exceed 4^{t}, and consequently the probability of the event that (ii) should fail is bounded from above by

4^{t} exp \{−\frac{1}{3}ε^{4}αt^{3/2}\} .  (346)

However, owing to the choice of t (cf. (343)), the quantity in (346) is smaller than 1/2. We conclude by Markov’s inequality that

the probability that (ii) fails is ≤ 1/2.  (347)

Now we turn our attention to property (iii). Let Ch be the random variable that counts the number of 2-paths P in 𝔽 with the two endpoints of P in A and the middle vertex of P in B. That is, let Ch(𝔽) be the number of 2-paths of the form {{a, b}, {b, a′}} in 𝔽, where a, a′ ∈ A and b ∈ B. Then, clearly,

𝔼(Ch(𝔽)) = \binom{t}{2}p^{2}t = α^{2}\binom{t}{2}.  (348)

This means that, by Markov’s inequality,

ℙ (Ch(𝔽) > α\binom{t}{2}) < α ≤ \frac{1}{2}.  (349)

Combining (347) and (349), we infer that there exists F with the following properties:

(a) for all A′ ⊂ A and B′ ⊂ B with |A| = a′ ≥ εt and |B′| = b′ ≥ εt, we have

||F [A′, B′]| − pa′b′| ≤ εpa′b′,  (350)

and hence (i) and (ii) hold, and

(b) Ch(F) ≤ α\binom{t}{2}, and hence (iii) holds.

The proof of Claim 29 is complete. □

We shall actually need a slight technical extension of Claim 29. To obtain this extension, note that, without loss of generality, we may assume that α and ε in the statement of Claim 29 are reciprocal of integers larger than 1. If we set

t = \frac{40}{ε^{8}α^{2}} ,  (351)

then (343) holds, and, moreover,

εt = \frac{40}{ε^{7}α^{2}}  (352)

is an integer. Thus, we have the following variant of Claim 29.

Claim 30. For every 0 < α < 1/2 and 0 < ε < 1/2 that are reciprocal of integers, there exist an integer t and a bipartite graph T = (A, B; F) with |A| = |B| = t satisfying properties (i)–(iii) of Claim 29 and such that

(iv) εt is an integer.

Proof of Theorem 27. Given α > 0 and ε > 0, let 0 < α′ ≤ α/2 and 0 < ε′ ≤ ε/2 be reciprocal of integers. We apply Claim 30 with constants α′ and ε′ to obtain t and the graph T = (A, B; F). Let p = α′/\sqrt{t}.

Let M_{0} ≫ t, and m_{0} = M_{0}t. Now, for a given m ≥ m_{0}, consider M such that

(M − 1)t < m ≤ Mt.  (353)

We construct the graph J as a ‘blow-up’ of T, replacing each vertex a ∈ A and b ∈ B of T by sets U_{a} and W_{b}, respectively, with U_{a} and W_{b} of cardinality M or M − 1. More precisely, consider pairwise disjoint sets U_{a} (a ∈ A), W_{b} (b ∈ B), each of cardinality M or M − 1, and set

U = ⋃_{a∈A} U_{a} and W = ⋃_{b∈B} W_{b}.  (354)

Let

E = {{u, w}: u ∈ U_{a}, w ∈ W_{b}, {a, b} ∈ F }.  (355)

Suppose we are given U′ ⊂ U and W′ ⊂ W with |U′| ≥ ε|U| and |W′| ≥ ε|W |. Since ε|U| = ε|W | = εMt is an integer, we may and shall assume that |U′| = |W′| = εMt.

Define a mapping μ: A ∪ B → [0, 1] by putting

μ(a) = \frac{1}{M} |U′ ∩ U_{a}| and μ(b) = \frac{1}{M} |W′ ∩ W_{b}|.  (356)

Since ∑_{a∈A} μ(a) = ∑_{b∈B} = μ(b) = εMt is an integer, we may apply Claim 28 to find sets A_{i} and B_{i} (i ∈ {0, 1}) such that (i)–(iii) in the statement of that claim holds. This however means that

(M − 1)^{2}|F [A_{0}, B_{0}]| ≤ |E[U′, W′]| ≤ M^{2}|F [A_{1}, B_{1}]|.  (357)

Since |A_{0}| = |B_{0}| = |A_{1}| = |B_{1}| = ε′t, we infer by Claim 30 that

|F [A_{1}, B_{1}]| ≤ \frac{α′}{\sqrt{t}}(1 + ε′)ε^{2}t^{2}  (358)

and

|F [A_{0}, B_{0}]| ≥ \frac{α′}{\sqrt{t}}(1 − ε′)ε^{2}t^{2}.  (359)

Consequently,

p(1 − ε) ≤ \frac{(M − 1)^{2}}{M^{2}} × \frac{α}{\sqrt{t}}(1 − ε′)

≤ \frac{|E[U′, W′]|}{|U′||W′|} ≤ \frac{α}{\sqrt{t}}(1 + ε′) ≤ p(1 + ε). (360)

In order to verify property (ii), observe that, for u ∈ U_{a} and u′ ∈ U_{a′}, we have that Γ_{J}(u) ∩ Γ_{J}(u′) = ∅ if and only if Γ_{T} (a) ∩ Γ_{T} (a′) = ∅. Hence

|\{\{u, u′\} ∈ \binom{U}{2}: Γ_{J}(u) ∩ Γ_{J}(u′) = ∅\}|

≥ (1 − α′)\binom{t}{2}(M − 1)^{2} ≥ (1 − α)\binom{m}{2}. (361)

This completes the proof of Theorem 27. □

References

[1] 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.4.1, 1.4.1, 1.4.1, 1.4.1

[2] N. Alon and F. R. K. Chung, Explicit construction of linear sized tolerant networks, Discrete Mathematics 72 (1988), no. 1-3, 15–19. MR 90f:05080 1

[3] 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.1, 4.2

[4] , The algorithmic aspects of the regularity lemma, J. Algorithms 16 (1994), no. 1, 80–109. MR 94j:05112 1.1, 4.2

[5] 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.1, 4.2

[6] József Beck, On size Ramsey number of paths, trees, and circuits I, Journal of Graph Theory 7 (1983), 115–129. 1.4.3

[7] , On size Ramsey number of paths, trees, and circuits II, Mathematics of Ramsey Theory, Algorithms and Combinatorics, vol. 5, Springer-Verlag, Berlin, 1990, pp. 34–45. 1.4.3

[8] Béla Bollobás, Random graphs, Academic Press Inc. [Harcourt Brace Jovanovich Publishers], London, 1985. MR 87f:05152 8

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

[10] Fan Chung and Ronald Graham, Sparse quasi-random graphs, Combinatorica 22 (2002), no. 2, 217–244, Special issue: Paul Erdős and his mathematics. MR 1 909 084 3

[11] 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.1, 4.2

[12] P. Erdős, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292–294. MR 8,479d 1.4.2 [13] , On the combinatorial problems which I would most like to see solved, Combinatorica

1 (1981), no. 1, 25–42. MR 82k:05001 1.4.3

[14] P. Erdős, R. J. Faudree, C. C. Rousseau, and R. H. Schelp, The size Ramsey number, Periodica Mathematica Hungarica 9 (1978), no. 2-2, 145–161. MR 80h:05037 1.4.3

[15] Paul Erdős and Joel Spencer, Probabilistic methods in combinatorics, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1974, Probability and Mathematical Statistics, Vol. 17. MR 52 #2895 1.1, 4.2

[16] P. Frankl and V. Rödl, Large triangle-free subgraphs in graphs without K_{4}, Graphs and Combinatorics 2 (1986), no. 2, 135–144. 1.4.2

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

[18] Ehud Friedgut and Michael Krivelevich, Sharp thresholds for certain Ramsey properties of random graphs, Random Structures Algorithms 17 (2000), no. 1, 1–19. MR 2001i:05136 1.4.2

[19] J. Friedman and N. Pippenger, Expanding graphs contain all small trees, Combinatorica 7 (1987), no. 1, 71–76. MR 88k:05063 1.4.3

[20] Z. Füredi, Random Ramsey graphs for the four-cycle, Discrete Mathematics 126 (1994), 407–410. 2

[21] A. Hajnal and E. Szemerédi, Proof of a conjecture of P. Erdős, Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969), North-Holland, Amsterdam, 1970, pp. 601–623. MR 45 #6661 3.4.2

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

[23] , Turán’s extremal problem in random graphs: forbidding even cycles, J. Combin. Theory Ser. B 64 (1995), no. 2, 273–287. MR 96e:05151 1.4.2, 2

[24] , Turán’s extremal problem in random graphs: forbidding odd cycles, Combinatorica 16 (1996), no. 1, 107–122. MR 97k:05180 1.4.2, 2

[25] Svante Janson, Tomasz Łuczak, and Andrzej Ruciński, Random graphs, Wiley-Interscience, New York, 2000. MR 2001k:05180 1.4.2, 1.4.2

[26] Y. Kohayakawa, Szemerédi’s regularity lemma for sparse graphs, Foundations of computational mathematics (Rio de Janeiro, 1997), Springer, Berlin, 1997, pp. 216–230. MR 99g:05145 3.2

[27] Y. Kohayakawa and B. Kreuter, Threshold functions for asymmetric Ramsey properties involving cycles, Random Structures Algorithms 11 (1997), no. 3, 245–276. MR 99g:05159 1.4.2, 2

[28] Y. Kohayakawa, B. Kreuter, and A. Steger, An extremal problem for random graphs and the number of graphs with large even-girth, Combinatorica 18 (1998), no. 1, 101–120. MR 2000b:05118 2

[29] Y. Kohayakawa, T. Łuczak, and V. Rödl, Arithmetic progressions of length three in subsets of a random set, Acta Arith. 75 (1996), no. 2, 133–163. MR 97b:11011 1.4.2, 2

[30] , On K^{4}-free subgraphs of random graphs, Combinatorica 17 (1997), no. 2, 173–213. MR 98h:05166 1.4.2, 1.4.2, 2, 18

[31] Y. Kohayakawa and V. Rödl, Regular pairs in sparse random graphs II, in preparation, 2001. 1.3.2, 4.3.4

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

[33] 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), János Bolyai Math. Soc., Budapest, 1996, pp. 295–352. MR 97d:05172 1

[34] T. Łuczak, personal communication, 1994. 1.2

[35] Tomasz Łuczak, Andrzej Ruciński, and Bernd Voigt, Ramsey properties of random graphs, J. Combin. Theory Ser. B 56 (1992), no. 1, 55–68. MR 94b:05172 1.4.2

[36] V. Rödl, On universality of graphs with uniformly distributed edges, Discrete Mathematics 59 (1986), no. 1-2, 125–134. 1

[37] V. Rödl, A. Ruciński, and A. Taraz, Hypergraph packing and graph embedding, Combinatorics, Probability and Computing 8 (1999), no. 4, 363–376. 1.4.1 [38] Vojtěch Rödl and Andrzej Ruciński, Lower bounds on probability thresholds for Ramsey

properties, Combinatorics—Paul Erdős is eighty, vol. 1 (Keszthely, 1993) (D. Miklós, V. T. Sós, and T. Szőnyi, eds.), Bolyai Society Mathematical Studies, János Bolyai Mathematical Society, Budapest, 1993, pp. 317–346. 1.4.2

[39] , Random graphs with monochromatic triangles in every edge coloring, Random Structures Algorithms 5 (1994), no. 2, 253–270. MR 95a:05102 1.4.2, 2

[40] , Threshold functions for Ramsey properties, J. Amer. Math. Soc. 8 (1995), no. 4, 917–942. MR 96h:05141 1.4.2, 2

[41] , Rado partition theorem for random subsets of integers, Proc. London Math. Soc. (3) 74 (1997), no. 3, 481–502. MR 98d:05147 2

[42] , Ramsey properties of random hypergraphs, Journal of Combinatorial Theory, Series A 81 (1998), no. 1, 1–33. MR 98m:05175 2

[43] Vojtěch Rödl and Endre Szemerédi, On size Ramsey numbers of graphs with bounded degree, Combinatorica 20 (2000), no. 2, 257–262. MR 1 767 025 1.4.3

[44] Joel Spencer, Three hundred million points suffice, J. Combin. Theory Ser. A 49 (1988), no. 2, 210–217. MR 90b:05116a 1.4.2

[45] , Erratum: “Three hundred million points suffice”, J. Combin. Theory Ser. A 50 (1989), no. 2, 323. MR 90b:05116b 1.4.2

[46] Endre Szemerédi, Regular partitions of graphs, Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), CNRS, Paris, 1978, pp. 399–401. MR 81i:05095 1, 1, 3.2

[47] 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, 1.1, 3, 4.2

[48] , 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.1, 3, 4.2

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