ON K^{4}-FREE SUBGRAPHS OF RANDOM GRAPHS

Y. Kohayakawa, T. Łuczak, and V. Rödl

Abstract. For 0 < γ ≤ 1 and graphs G and H, write G →_{γ} H if any γ-proportion of the edges of G span at least one copy of H in G. As customary, write K^{r} for the complete graph on r vertices. We show that for every fixed real η > 0 there exists a constant C = C(η) such that almost every random graph G_{n,p} with p = p(n) ≥ Cn^{−2/5} satisfies G_{n,p} →_{2/3+η} K^{4}. The proof makes use of a variant of Szemerédi’s regularity lemma for sparse graphs and is based on a certain superexponential estimate for the number of pseudo-random tripartite graphs whose triangles are not too well distributed. Related results and a general conjecture concerning H-free subgraphs of random graphs in the spirit of the Erdős–Stone–Simonovits theorem are discussed.

§0. Introduction

A classical area of extremal graph theory investigates numerical and structural problems concerning H-free graphs, namely graphs that do not contain a copy of a given fixed graph H as a subgraph. Let ex(n, H) be the maximal number of edges that an H-free graph on n vertices may have. A basic question is then to determine or estimate ex(n, H) for any given H and large n. A solution to this problem is given by the celebrated Erdős–Stone–Simonovits theorem, which states that, as n → ∞, we have

ex(n, H) = (1 − \frac{1}{χ(H) − 1} + o(1)) \binom{n}{2},  (1)

where as usual χ(H) is the chromatic number of H. Furthermore, as proved independently by Erdős and Simonovits, every H-free graph G = G^{n} that has as many edges as in (1) is in fact ‘very close’ (in a certain precise sense) to the densest n-vertex (χ(H) − 1)-partite graph. For these and related results, see, for instance, Bollobás [2].

Here we are interested in a variant of the function ex(n, H). Let G and H be graphs, and write ex(G, H) for the maximal number of edges that an H-free subgraph of G may have. Formally, ex(G, H) = max{e(J): H ⊄ J ⊂ G}, where e(J) stands for the size |E(J)| of J. Clearly ex(n, H) = ex(K^{n}, H). As an example of

1991 Mathematics Subject Classification. Primary 05C80, 05C35; Secondary 05D99. Key words and phrases. Turán’s extremal problem, forbidden subgraphs, extremal subgraphs,

cliques, random graphs.

The first author was partially supported by FAPESP (Proc. 93/0603–1) and by CNPq (Proc. 300334/93–1 and ProTeM–CC–II Project ProComb). Part of this work was done while the second author was visiting the University of São Paulo, supported by FAPESP (Proc. 94/4276–8). The third author was partially supported by the NSF grant DMS–9401559.

Typeset by AMS-TEX

a problem involving ex(G, H) with G ≠ K^{n}, let us recall that a well-known conjecture of Erdős states that ex(Q^{n}, C^{4}) = (1/2 + o(1))e(Q^{n}), where Q^{n} stands for the n-dimensional hypercube and C^{4} is the 4-cycle. (For several results concerning this conjecture, see Chung [4].)

Our aim here is to study ex(G, H) when G is a ‘typical’ graph, by which we mean a random graph. Let 0 < p = p(n) ≤ 1 and 0 < M = M(n) ≤ N = \binom{n}{2} be given. The standard binomial random graph G_{p} = G_{n,p} has as vertex set a fixed set V (G_{p}) of cardinality n and two such vertices are adjacent in G_{p} with probability p, with all such adjacencies independent. The random graph G_{M} = G_{n,M} is simply a graph on a fixed n-element vertex set V (G_{M}) chosen uniformly at random from all the \binom{N}{M} possible candidates. (For concepts and results concerning random graphs not given in detail below, see e.g. Bollobás [3].) Here we wish to investigate the random variables ex(G_{n,p}, H) and ex(G_{n,M}, H).

Let H be a graph of order |H| = |V (H)| ≥ 3. Let us write d_{2}(H) for the 2-density of H, that is

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

Given a real 0 ≤ ε ≤ 1 and an integer r ≥ 2, let us say that a graph J is ε-quasi r-partite if J may be made r-partite by the deletion of at most εe(J) of its edges. A general conjecture concerning ex(G_{n,p}, H) is as follows. For simplicity, below we restrict our attention to the binomial random graph G_{n,p}. Much of what follows may be restated in terms of G_{n,M}. As is usual in the theory of random graphs, we say that a property P holds almost surely or that almost every random graph G_{n,p} or G_{n,M} satisfies P if P holds with probability tending to 1 as n → ∞.

Conjecture 1. Let H be a non-empty graph of order at least 3, and let 0 < p = p(n) ≤ 1 be such that pn^{1/d_{2}(H)} → ∞ as n → ∞. Then the following assertions hold.

(i) Almost every G_{n,p} satisfies

ex(G_{n,p}, H) = (1 − \frac{1}{χ(H) − 1} + o(1)) e(G_{n,p}).  (2)

(ii) Suppose χ(H) ≥ 3. Then for any ε > 0 there is a δ = δ(ε) > 0 such that almost every G_{n,p} has the property that any H-free subgraph J ⊂ G_{n,p} of G_{n,p} with e(J) ≥ (1 − δ) ex(G_{n,p}, H) is ε-quasi (χ(H) − 1)-partite.

Recall that any graph G contains an r-partite subgraph J ⊂ G with e(J) ≥ (1 − 1/r)e(G). Thus the content of Conjecture 1(i) is that ex(G_{n,p}, H) is at most as large as the right-hand side of (2), or, in other words, that G_{n,p} →_{γ} H holds almost surely for any fixed γ > 1−1/(χ(H)−1). There are a few results in support of Conjecture 1(i).

K^{4}-FREE SUBGRAPHS OF RANDOM GRAPHS 3

Any result concerning the tree-universality of expanding graphs or else a simple application of Szemerédi’s regularity lemma for sparse graphs (see Lemma 4 below) give Conjecture 1(i) for forests. The cases in which H = K^{3} and H = C^{4} are essentially proved in Frankl and Rödl [5] and Füredi [6], respectively, in connection with problems concerning the existence of some graphs with certain extremal properties. The case in which H is a general cycle was settled by Haxell, Kohayakawa, and Łuczak [8, 9] (see also Kohayakawa, Kreuter, and Steger [11]). Conjecture 1(ii) in the case in which 0 < p < 1 is a constant follows easily from Szemerédi’s regularity lemma [15]. A variant of this lemma for sparse graphs (cf. Lemma 4 below) and a lemma from Kohayakawa, Łuczak, and Rödl [12] concerning induced subgraphs of bipartite graphs may be used to verify Conjecture 1 for H = K^{3} in full. (See comments following Conjecture 23 for further details.) Still in the case in which H = K^{3}, for 0 < p < 1 sufficiently close to 1/2, a much stronger result than Conjecture 1(ii) was proved by Babai, Simonovits, and Spencer [1]. Finally, let us note that a result concerning Ramsey properties of random graphs in the spirit of Conjecture 1 was proved by Rödl and Ruciński [13, 14].

Here we prove Conjecture 1(i) for H = K^{4}. Our results are as follows.

Theorem 2. For any constant 0 < η ≤ 1/3, there is a constant C = C(η) for which the following holds. If 0 ≤ p = p(n) ≤ 1 is such that p ≥ Cn^{−2/5} for all large enough n, then almost every G_{p} = G_{n,p} is such that G_{p} →_{2/3+η} K^{4}.

Corollary 3. For any constant 0 < η ≤ 1/3, there is a constant C = C(η) for which the following holds. If 0 ≤ M = M(n) ≤ \binom{n}{2} is such that M ≥ Cn^{8/5} for all large enough n, then almost every G_{M} = G_{n,M} is such that G_{M} →_{2/3+η} K^{4}.

In §6 below, we formulate an auxiliary conjecture (Conjecture 23) that, if proved, would imply Conjecture 1 in full for all graphs H.

Finally, let us mention that Conjecture 1, if true, would immediately imply the existence of very ‘sparse’ graphs G satisfying the property that G →_{γ} H for any γ > 1 − 1/(χ(H) − 1). A simple corollary of Theorem 2 is that, for any η > 0, there is a graph G = G_{η} that contains no K^{5} but we have G →_{2/3+η} K^{4} (see §5). Erdős and Nešetřil have asked whether such graphs exist.

This note is organised as follows. In Section 1.1 we give a short outline of the proof of our main result, Theorem 2, and in Section 1.2, some preliminary results are given. In §2 the distribution of triangles in random and pseudo-random graphs is studied. In §3 we prove a key lemma in the proof of our main result, Lemma 16. Theorem 2 is proved in §4. In §5 we discuss a deterministic corollary to Theorem 2 concerning the Erdős–Nešetřil problem. Our last paragraph contains Conjecture 23.

§1. Outline of Proof and Preliminaries

1.1. Outline of the proof of Theorem 2. The proof of our main result is somewhat long and hence, for convenience, in this section we describe its main steps. Here we try to avoid being too technical.

The proof of Theorem 2 naturally splits into two parts. Suppose p = p(n) ≥ Cn^{−2/5}, where C is some large constant, and let H be a spanning subgraph of G_{p} = G_{n,p} with ‘relative density’ e(H)/e(G_{p}) ≥ λ. Let us say that two vertices x, y ∈ G_{p} are K_{−}^{4}-connected by H if there are two other vertices z_{1}, z_{2} ∈ H such that both {x, z_{1}, z_{2}} and {z_{1}, z_{2}, y} induce triangles in H. Sometimes we also say that such a pair xy is a pivotal pair.

In the first part of our proof, we show that the number of pairs of vertices x, y ∈ G_{p} that are K_{−}^{4}-connected by H is roughly at least (2λ − 1)\binom{n}{2}, as long as C is a large enough constant. The precise statement of this result is given in Section 3.2, Lemma 16. The second part of the proof consists of deducing our Theorem 2 from Lemma 16. This part is less technical than the first, and is also considerably shorter. The method used here was inspired by an argument in Rödl and Ruciński [14], and a version of this technique was used in Haxell, Kohayakawa, and Łuczak [8]. Let us give a brief description of this method.

Thus let G_{p} = G_{n,p} be the binomial random graph with p = p(n) ≥ Cn^{−2/5}, where C is some large constant, and let a constant 0 < η ≤ 1/3 be fixed. For simplicity, let us also assume that p = p(n) → 0 as n → ∞. We may write G_{p} as the union of k independent random graphs G_{p_{1}}^{(j)} (1 ≤ j ≤ k), where k is some large constant to be carefully chosen later. Since p = o(1), below we may ignore the edges of G_{p} = G_{p_{1}}^{(1)} ∪⋯∪G_{p_{1}}^{(k)} that belong to more than one of the G_{p_{1}}^{(j)}. Let us now ask an ‘adversary’ to choose a subgraph H ⊂ G_{p} of G_{p} of size at least λe(G_{p}), where λ = 2/3 + η, or, equivalently, let us ask our adversary to choose a set of edges F ⊂ E(G_{p}) with |F | ≥ λe(G_{p}). Our aim is to show that such a set F must span a K^{4}.

Instead of asking our adversary to pick F directly, we ask him to pick F ∩ E(G_{p_{1}}^{(j)}) for all j. For some j_{0}, we must have |F ∩ E(G_{p_{1}}^{(j_{0})}))| ≥ λe(G_{p_{1}}^{(j_{0})}). We may in fact ask our adversary to pick first j_{0} and F_{j_{0}} = F ∩ E(G_{p_{1}}^{(j_{0})}), and leave the choice of F ∩ E(G_{p_{1}}^{(j)}) (j ≠ j_{0}) for later. By Lemma 16, we know that at least ∼ (2λ − 1)\binom{n}{2} = (1/3 + 2η)\binom{n}{2} edges of K^{n} join pairs of vertices that are K_{−}^{4}-connected by F_{j_{0}}. We now show G′ = ⋃_{j≠j_{0}} G_{p_{1}}^{(j)} to our adversary, and ask him to pick F ∩E(G′). Note that, with very high probability, at least 1/3+η of the edges of G′ will be formed by K_{−}^{4}-connected pairs, and if our adversary puts any of these edges into F ∩ E(G′), then F will span a copy of K^{4}. However, since G′ contains an extremely large proportion of the edges of G_{p} (we choose k very large), our adversary is forced to pick at least 2/3 of the edges of G′, and hence he is forced to ‘close’ a K^{4} by picking a K_{−}^{4}-connected pair xy for an edge of H.

Let us close this section with a few words on the proof of Lemma 16. Recall that in that lemma we are concerned with estimating the number of K_{−}^{4}-connected pairs induced by subgraphs of random graphs. A very simple lower bound for the number of such pairs induced by an arbitrary graph H_{∗} is given in assertion (*) in Section 3.1. This estimate is far too weak to be of any use when dealing with subgraphs of random graphs, but a weighted version of this estimate, Lemma 15, is important in the proof of Lemma 16. Another important and a much deeper ingredient in the proof of Lemma 16 is a version of Szemerédi’s regularity lemma [15] for sparse graphs; see Lemma 4 in Section 1.2 below. A simple application of Lemmas 4 and 15 allows us to focus our attention on certain ε-regular quadruples. The key lemma concerning such quadruples is Lemma 17 in Section 3.2. The proof of Lemma 17 is based on certain results concerning the number and the distribution of triangles in random and pseudo-random graphs. Paragraph 2 is entirely devoted to those results. The main lemmas in §2 are Lemmas 7 and 10.

1.2. Preliminaries. Let a graph H = H^{n} of order |H| = n be fixed. For U, W ⊂ V = V (H) with U ∩ W = ∅, we write E(U, W) = E_{H}(U, W) for the set of edges of H that have one endvertex in U and the other in W. We set e(U, W) = e_{H}(U, W) = |E(U, W)|.

The following notion will be needed in what follows. Suppose 0 < η ≤ 1 and 0 < p ≤ 1. We say that H is η-upper-uniform with density p if, for all U, W ⊂ V with U ∩ W = ∅ and |U|, |W | ≥ ηn, we have e_{H}(U, W) ≤ (1 + η)p|U||W |. Clearly, if H is η-upper-uniform with density p, then it is also η′-upper-uniform with density p′ for any η ≤ η′ ≤ 1 and any p ≤ p′ ≤ 1. In the sequel, for any two disjoint non-empty sets U, W ⊂ V, let

d_{H,p}(U, W) = e_{H}(U, W)/p|U||W |

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

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

We say that a partition P = (V_{i})_{0}^{k} of V = V (H) is (ε, k)-equitable if |V_{0}| ≤ εn, and |V_{1}| = … = |V_{k}|. Also, we say that V_{0} is the exceptional class of P. When the value of ε is not relevant, we refer to an (ε, k)-equitable partition as a k-equitable partition. Similarly, P is an equitable partition of V if it is a k-equitable partition for some k. Finally, we say that an (ε, k)-equitable partition P = (V_{i})_{0}^{k} of V is (ε, H, p)-regular if at most ε\binom{k}{2} pairs (V_{i}, V_{j}) with 1 ≤ i < j ≤ k are not (ε, p)- regular. We may now state an extension of Szemerédi’s lemma [15] to subgraphs of η-upper-uniform graphs.

Lemma 4. For any given ε > 0 and k_{0} ≥ 1, there are constants η = η(ε, k_{0}) > 0 and K_{0} = K_{0}(ε, k_{0}) ≥ k_{0} that depend only on ε and k_{0} such that any η-upper-uniform graph H with density 0 < p ≤ 1 admits an (ε, H, p)-regular (ε, k)-equitable partition of its vertex set with k_{0} ≤ k ≤ K_{0}. □

Using standard estimates for tails of the binomial distribution, it is easy to check that a.e. G_{n,p} is η-upper-uniform with density p for any constant 0 < η ≤ 1 if d = pn is larger than some constant d_{0} = d_{0}(η).

Let us introduce a piece of notation before we proceed. If U_{1}, …, U_{ℓ} ⊂ V (J) are pairwise disjoint sets of vertices of a given graph J, we write J[U_{1}, …, U_{ℓ}] for the ℓ-partite subgraph of J naturally defined by the U_{i} (1 ≤ i ≤ ℓ). Thus, J[U_{1}, …, U_{ℓ}] has vertex set ⋃_{1}^{ℓ} U_{i} and two of its vertices are adjacent if and only if they are adjacent in J and, moreover, they belong to distinct U_{i}.

Now suppose we have real numbers 0 < p ≤ 1, 0 < ε ≤ 1, 0 < γ_{0} ≤ 1 and an integer m ≥ 1. Suppose the above U_{i} (1 ≤ i ≤ ℓ) all have cardinality m, and write γ_{ij} for the p-density d_{J,p}(U_{i}, U_{j}) for all distinct i and j. Suppose L is a graph on [ℓ] = {1, …, ℓ} such that, for any 1 ≤ i < j ≤ ℓ, the pair (U_{i}, U_{j}) is (ε, J, p)-regular and γ_{ij} ≥ γ_{0} whenever ij ∈ E(L).

We may now state our next lemma. In what follows, we write O_{1}(x) for any term y satisfying |y| ≤ x. Also, as usual, we write Δ = Δ(L) for the maximal degree of L and we write Γ_{J}(x) for the J-neighbourhood of a vertex x ∈ V (J).

Lemma 5. Let J, L, and the sets U_{i} (1 ≤ i ≤ ℓ) be as above and let Δ = Δ(L). Suppose 0 < ε ≤ 1/(2Δ + 1) and put ρ = (2Δ + 1/γ_{0})ε and μ = 2Δε. Then there are sets Ū_{i} ⊂ U_{i} with |Ū_{i}| ≥ (1 − μ)m for all 1 ≤ i ≤ ℓ such that, for all x ∈ Ū_{i} and any 1 ≤ i ≤ ℓ, we have

d_{ij}(x) = |Γ_{J}(x) ∩ Ū_{j}| = (1 + O_{1}(ρ))γ_{ij}pm  (3)

for any j with ij ∈ E(L). □

Lemma 5 above is very similar to Lemma 2 in [7], and hence its rather elementary proof is omitted. We close this section with a very simple large deviation inequality for the hypergeometric distribution. This inequality will be used in Section 2.1 below.

Lemma 6. Let 1 ≤ a ≤ n and 1 ≤ t ≤ r ≤ n be integers, and suppose R ⊂ [n] is an r-element subset of [n] = {1, …, n} chosen uniformly at random. Then

ℙ(|R ∩ [a]| ≥ t) ≤ (\frac{a}{n − r + 1})^{t} \binom{r}{t}. □

§2. Triangles in Pseudo-Random and Random Graphs

2.1. The counting lemma. Let m ≥ 1 be an integer. In this section we shall consider a fixed triple V = (V̄_{1}, V̄_{2}, V̄_{3}) of pairwise disjoint sets with m/2 ≤ m_{i} = |V̄_{i}| ≤ m for all i ∈ {1, 2, 3}. We shall also suppose that 0 < p = p(m) ≤ 1 satisfies pm ≥ m^{1/2+1/ log log log m} for all large enough m and, moreover, that p = o(1) as m → ∞. In this section, all the asymptotic notation refers to m → ∞. Our aim is to estimate from above the number of certain pseudo-random tripartite graphs F with tripartition V (F) = V̄_{1} ∪ V̄_{2} ∪ V̄_{3} that contain unexpectedly few triangles given the number of edges that they have, or else whose triangles are not too regularly distributed.

Before we may describe precisely which graphs F are of interest to us, we need to introduce a few definitions. In what follows, indices will be tacitly taken modulo 3 when convenient. Let 0 < δ ≤ 1 be given. Suppose e ∈ E_{F} (V̄_{i−1}, V̄_{i+1}) = E(F [V̄_{i−1}, V̄_{i+1}]) (i ∈ {1, 2, 3}) and let k_{3}(e) = k_{3}^{F} (e) be the number of triangles of F that contain e. We shall say that e is (δ, K^{3})-poor if

k_{3}(e) < (1 − δ)d_{F,p}(V̄_{i}, V̄_{i−1})d_{F,p}(V̄_{i}, V̄_{i+1})p^{2}m_{i}.

The graph F is (δ, K^{3})-unbalanced if, for some i ∈ {1, 2, 3}, the number of (δ, K^{3})- poor edges in E_{F} (V̄_{i−1}, V̄_{i+1}) is at least δe_{F} (V̄_{i−1}, V̄_{i+1}) = δ|E_{F} (V̄_{i−1}, V̄_{i+1})|. For simplicity, below we write γ_{i} = d_{F,p}(V̄_{i−1}, V̄_{i+1}) (i ∈ {1, 2, 3}) and, if x ∈ V̄_{i} and i ≠ j ∈ {1, 2, 3}, we let d_{ij}(x) = |Γ_{F} (x) ∩ V̄_{j}|.

Now suppose integers m and T and real constants 0 < ε̄ ≤ 1, 0 < γ̄_{0} ≤ 1, and 0 < ρ̄ ≤ 1 are given, and let V = (V̄_{1}, V̄_{2}, V̄_{3}) and m = (m_{1}, m_{2}, m_{3}) be as above. Let us write F_{p}(ε̄, γ̄_{0}, ρ̄, T) = F_{p}(ε̄, γ̄_{0}, ρ̄; V, T) for the set of tripartite graphs F with tripartition V (F) = V̄_{1} ∪V̄_{2} ∪V̄_{3} that satisfy the following properties:

(i) (V̄_{1}, V̄_{2}, V̄_{3}) is an (ε̄, F, p)-regular triple, (ii) γ̄_{0} ≤ γ_{i} = d_{F,p}(V̄_{i−1}, V̄_{i+1}) ≤ 2 for all i ∈ {1, 2, 3}, (iii) d_{ij}(x) = |Γ_{F} (x) ∩ V̄_{j}| = (1 + O_{1}(ρ̄))γ_{k}pm_{j} for all x ∈ V̄_{i} and any choice of i,

j, and k such that {i, j, k} = [3], (iv) F has size e(F) = |E(F)| = T.

Moreover, for any given 0 < δ ≤ 1, let F_{p}^{δ}(ε̄, γ̄_{0}, ρ̄, T) = F_{p}^{δ}(ε̄, γ̄_{0}, ρ̄; V, T) be the set of (δ, K^{3})-unbalanced graphs F in F_{p}(ε̄, γ̄_{0}, ρ̄, T). Put

f_{p}^{δ}(ε̄, γ̄_{0}, ρ̄; m, T) = |F_{p}^{δ}(ε̄, γ̄_{0}, ρ̄; V, T)|.

Sometimes the labelling of the vertices of the graphs in F_{p}(ε̄, γ̄_{0}, ρ̄; V, T) or in F_{p}^{δ}(ε̄, γ̄_{0}, ρ̄; V, T) is not relevant, and in that case we may replace V by m in our notation.

Our crucial counting lemma is as follows.

Lemma 7. Let 0 < α ≤ 1, 0 < γ̄_{0} ≤ 1, and 0 < δ ≤ 1 be given. Then there is a constant ε_{0} = ε_{0}(α, γ̄_{0}, δ) > 0 that depends only on α, γ̄_{0}, and δ for which the following holds. Suppose 0 < p = p(m) ≤ 1 is such that p ≥ m^{−1/2+1/ log log log m} for all large enough m and, moreover, p = o(1) as m → ∞. Then, if ρ̄ ≤ ρ̄_{0} = δ/27, ε̄ ≤ ε_{0}, and m is sufficiently large, we have

f_{p}^{δ}(ε̄, γ̄_{0}, ρ̄; m, T) = |F_{p}^{δ}(ε̄, γ̄_{0}, ρ̄; m, T)| ≤ α^{T} \binom{3m^{2}}{T}

for all T and all m = (m_{1}, m_{2}, m_{3}) with m/2 ≤ m_{i} ≤ m (i ∈ {1, 2, 3}).

Most of the rest of Section 2.1 is dedicated to the proof of Lemma 7 above. Our general strategy in this proof is as follows. We randomly generate a tripartite graph F with tripartition V (F) = V̄_{1}∪V̄_{2}∪V̄_{3} and size e(F) = |E(F)| = T, and show that the probability that the graph we obtain will be a member of F_{p}^{δ}(ε̄, γ̄_{0}, ρ̄, T) is suitably small. We generate F in steps: we first generate F [V̄_{2}, V̄_{3}]. We then generate F [V̄_{1}, V̄_{3}] and analyse the structure of the graph F [V̄_{1}, V̄_{3}] ∪ F [V̄_{2}, V̄_{3}]. We then finally generate F [V̄_{1}, V̄_{2}] and show that the appropriate probability is indeed small.

Let us now make precise the process by which we generate F. We first of all fix a partition T = T_{1} + T_{2} + T_{3} of T such that, putting γ_{i} = T_{i}/pm_{i−1}m_{i+1}, we have γ̄_{0} ≤ γ_{i} ≤ 2 for all i ∈ {1, 2, 3}. Note that, because of condition (ii) above for F, we may disregard the T for which such a partition does not exist. Let us suppose that the bipartite graph F_{23} = F [V̄_{2}, V̄_{3}] has been fixed, and that the following properties hold (cf. (i)–(iv) above): (a) the pair (V̄_{2}, V̄_{3}) is (ε̄, F_{23}, p)- regular, (b) d_{ij}(x) = |Γ_{F_{23}}(x)∩V̄_{j}| = (1+O_{1}(ρ̄))γ_{1}pm_{j} for all x ∈ V̄_{i}, where {i, j} = {2, 3}, and (c) e(F_{23}) = T_{1}.

We now fix the degree sequence for the vertices x ∈ V̄_{1} in the bipartite graph F [V̄_{1}, V̄_{3}], and generate this graph respecting this sequence. Thus let (d_{13}(x))_{x∈V̄_{1}} with ∑_{x∈V̄_{1}} d_{13}(x) = T_{2} and d_{13}(x) = (1 + O_{1}(ρ̄))γ_{2}pm_{3} for all x ∈ V̄_{1} be fixed, and generate the bipartite graph F_{13} = F [V̄_{1}, V̄_{3}] by selecting the neighbourhoods Γ_{F_{13}}(x) ⊂ V̄_{3} (x ∈ V̄_{1}) randomly and independently for all x ∈ V̄_{1}. Thus, for every x ∈ V̄_{1}, all the d_{13}(x)-element subsets of V̄_{3} are equally likely to be chosen as the neighbourhood of x within V̄_{3}. We now analyse the structure of F_{13} ∪ F_{23} = F [V̄_{1}, V̄_{3}] ∪ F [V̄_{2}, V̄_{3}].

For convenience, let us put d_{ij} = Ave_{x∈V̄_{i}} d_{ij}(x) = T_{k}/m_{i} = γ_{k}pm_{j} for all i, j, and k with {i, j, k} = [3] and k ≠ 3. Put also d_{13} = γ_{2}pm_{3} and d_{23} = γ_{1}pm_{3}. Thus d_{13}(x) = (1 + O_{1}(ρ̄))d_{13} for all x ∈ V̄_{1}, and d_{23}(y) = (1 + O_{1}(ρ̄))d_{23} for all y ∈ V̄_{2}.

Let 0 < β_{1} ≤ 1 be given. For all x ∈ V̄_{1}, put

Ṽ_{2} = Ṽ_{2}(x, β_{1}) = {y ∈ V̄_{2}: σ(x, y) ≤ −β_{1}d_{13}d_{23}/m_{3}},

where σ(x, y) = d(x, y) − d_{13}d_{23}/m_{3} = |Γ_{F_{13}}(x) ∩ Γ_{F_{23}}(y)| − d_{13}d_{23}/m_{3}. Note that the set Ṽ_{2}(x, β_{1}) is defined in such a way that the following fact holds: if e = xy (x ∈ V̄_{1}, y ∈ V̄_{2}) is an edge of F, then e is a (β_{1}, K^{3})-poor edge if and only if y ∈ Ṽ_{2}(x, β_{1}).

Now let 0 < β_{2} ≤ 1 be given. Below we say that x ∈ V̄_{1} is (β_{1}, β_{2})-faulty if |Ṽ_{2}(x, β_{1})| ≥ β_{2}m_{2}. Note that, clearly, since we are conditioning on F_{23} = F [V̄_{2}, V̄_{3}], the event that a vertex x ∈ V̄_{1} should be (β_{1}, β_{2})-faulty depends only on the random set Γ_{F_{13}}(x) ⊂ V̄_{3} that is chosen as the neighbourhood of x within V̄_{3}.

Our next lemma is the key technical result in the proof of the main lemma in this section, Lemma 7.

Lemma 8. Suppose the constants 0 < β_{1} ≤ 1, 0 < β_{2} ≤ 1, 0 < γ̄_{0} ≤ 1, 0 < ε̄ ≤ 1, and 0 < ρ̄ ≤ 1 are such β_{1}β_{2} ≥ 27ε̄, β_{2}ρ̄ ≤ ε̄, and β_{2} ≤ γ̄_{0}. Then, for all sufficiently large m, the probability that a given vertex x ∈ V̄_{1} is (β_{1}, β_{2})-faulty is at most (5ε̄^{ε̄/β_{2}})^{d_{13}}.

Proof. Let us fix x ∈ V̄_{1}, and assume that |Ṽ_{2}| = |Ṽ_{2}(x, β_{1})| ≥ β_{2}m_{2}. Let Ṽ_{2}^{0} ⊂ Ṽ_{2} be such that m̃_{2} = |Ṽ_{2}^{0}| = ⌈β_{2}m_{2}⌉. The following assertion, whose proof we omit, is very similar to Lemma 5.

Assertion 1. There exist sets V̄′_{2} ⊂ Ṽ_{2}^{0} and V̄′_{3} ⊂ V̄_{3} for which we have m′_{2} = |V̄′_{2}| ≥ (1 − 2ε̄/β_{2})m̃_{2} and m′_{3} = |V̄′_{3}| ≥ (1 − 2ε̄)m_{3}, and furthermore

d′_{23}(y) = |Γ_{F_{23}}(y) ∩ V̄′_{3}| = (1 + O_{1} (\frac{3ε̄}{β_{2}})) d_{23}  (4)

for all y ∈ V̄′_{2}, and

d′_{32}(z) = |Γ_{F_{23}}(z) ∩ V̄′_{2}| = (1 + O_{1} (\frac{3ε̄}{β_{2}})) β_{2}d_{32}  (5)

for all z ∈ V̄′_{3}.

Using Assertion 1, we prove next that there exists a small set Y of vertices from Ṽ_{2} whose F_{23}-neighbourhood uniformly cover essentially all of V̄_{3}. We need to introduce some notation. Let us set ω = ω(m) = m^{1/ log log m}, and let d^{Y} (z) = |Γ_{F_{23}}(z) ∩ Y | for all Y ⊂ V̄_{2} and all z ∈ V̄_{3}. Put also

V̄′′_{3} = V̄′′_{3}(Y) = \{z ∈ V̄_{3}: d^{Y} (z) = (1 + O_{1} (\frac{4ε̄}{β_{2}})) ω\}

for all Y ⊂ V̄_{2}. Assertion 2. There is a set Y ⊂ Ṽ_{2} of cardinality q = |Y | = (1+O_{1}(3ε̄/β_{2}))ωm_{2}/d_{32} such that |V̄′′_{3}| = |V̄′′_{3}(Y)| ≥ (1 − 2ε̄)m_{3}, and such that

d′′_{23}(y) = |Γ_{F_{23}}(y) ∩ V̄′′_{3}| ≥ (1 − \frac{3ε̄}{β_{2}}) d_{23}  (6)

for all y ∈ Y. Let V̄′_{2} and V̄′_{3} be as in Assertion 1. To prove Assertion 2, we construct Y by randomly selecting its elements from the set V̄′_{2} ⊂ Ṽ_{2}. Let p_{Y} = p_{Y} (m) = ω/β_{2}d_{32}. Note that 0 < p_{Y} < 1 for all large enough m. Put the vertices of V̄′_{2} into Y randomly, each with probability p_{Y}, and with all these events independent. The expected cardinality of Y is then

𝔼(|Y |) = (1 + O_{1} (\frac{2ε̄}{β_{2}})) \frac{ωm_{2}}{d_{32}} ,

and the expected degree of a vertex z ∈ V̄′_{3} into Y is

𝔼(d^{Y} (z)) = (1 + O_{1} (\frac{3ε̄}{β_{2}})) ω.

From standard bounds for the tail of the binomial distribution, we may deduce that there is a set Y ⊂ V̄′_{2} ⊂ Ṽ_{2} such that q = |Y | is as required in Assertion 2, and such that every z ∈ V̄′_{3} satisfies d^{Y} (z) = (1 + O_{1}(4ε̄/β_{2}))ω. Note that, for such a set Y, we have V̄′_{3} ⊂ V̄′′_{3} = V̄′′_{3}(Y), and hence |V̄′′_{3}| ≥ |V̄′_{3}| ≥ (1 − 2ε̄)m_{3}. It now suffices to notice that every y ∈ Y is such that

d′′_{23}(y) = |Γ_{F_{23}}(y) ∩ V̄′′_{3}| ≥ |Γ_{F_{23}}(y) ∩ V̄′_{3}| ≥ (1 − \frac{3ε̄}{β_{2}}) d_{23},

since y ∈ Y ⊂ V̄′_{2} and relation (4) in Assertion 1 holds. This completes the proof of Assertion 2. Assertion 3. The probability that our fixed vertex x ∈ V̄_{1} admits a set Y as in Assertion 2 is at most (4ε̄^{ε̄/β_{2}})^{d_{13}}. Let us first sketch the idea in the proof of Assertion 3. Roughly speaking, the set Y is such that the neighbourhoods Γ_{F_{23}}(y) ∩ V̄′′_{3} of the vertices y ∈ Y within V̄′′_{3} are about of the same size, and the vertices in V̄′′_{3} are, by definition, covered by those sets quite uniformly. Now, since the vertices in Y are all in Ṽ_{2}, we have that the neighbourhood Γ_{F_{13}}(x) of x within V̄_{3} intersects all the neighbourhoods Γ_{F_{23}}(y) (y ∈ Y) too little. Thus it intersects the sets Γ_{F_{23}}(y) ∩ V̄′′_{3} too little as well, and this is possible only if it in fact intersects V̄′′_{3} in an unexpectedly small set. It then suffices to estimate the probability that Γ_{F_{13}}(x) ∩ V̄′′_{3} should be as small. Let us now formalise the argument above.

Assume that a set Y as in Assertion 2 exists. We consider the vectors g = g^{x} = (g_{z})_{z∈V̄′′_{3}} and f^{y} = (f_{z}^{y})_{z∈V̄′′_{3}} (y ∈ Y) with entries

g_{z} = \{ \begin{matrix}1 & if z ∈ Γ_{F_{13}}(x) \\ −d_{13}/m_{3} & otherwise, \end{matrix}

and

f_{z}^{y} = \{ \begin{matrix}1 & if z ∈ Γ_{F_{23}}(y) \\ −d_{23}/m_{3} & otherwise. \end{matrix}

We first estimate ξ_{z} = ∑_{y∈Y} f_{z}^{y} for z ∈ V̄′′_{3}. For any fixed z ∈ V̄′′_{3}, we have

ξ_{z} = ∑_{y∈Y} f_{z}^{y} = d^{Y} (z) − \frac{d_{23}}{m_{3}} \{q − d^{Y} (z)\} = (1 + \frac{d_{23}}{m_{3}} ) d^{Y} (z) − \frac{d_{23}q}{m_{3}}

= (1 + \frac{d_{23}}{m_{3}} ) (1 + O_{1} (\frac{4ε̄}{β_{2}})) ω − \frac{d_{23}q}{m_{3}} .

We have d_{23} = γ_{1}pm_{3} = o(m_{3}), and, since d_{23}/m_{3} = T_{1}/m_{2}m_{3} = d_{32}/m_{2}, we have d_{23}q/m_{3} = (1 + O_{1}(3ε̄/β_{2}))ω. Therefore

ξ_{z} ≤ (1 + o(1)) (1 + \frac{4ε̄}{β_{2}}) ω − (1 − \frac{3ε̄}{β_{2}}) ω ≤ \frac{8ε̄}{β_{2}}ω

for large enough m, and similarly ξ_{z} ≥ −(8ε̄/β_{2})ω if m is sufficiently large. Given two vectors a = (a_{z})_{z∈V̄′′_{3}} and b = (b_{z})_{z∈V̄′′_{3}}, let ⟨a, b⟩ = ∑_{z∈V̄′′_{3}} a_{z}b_{z}. We now estimate ∑_{y∈Y} ⟨f^{y}, g⟩. We have

∑_{y∈Y}⟨f^{y}, g⟩ = ⟨∑_{y∈Y} f^{y}, g⟩ = ⟨(ξ_{z})_{z∈V̄′′_{3}}, g⟩ = ∑_{z∈V̄′′_{3}} ξ_{z}g_{z}.

Therefore

| ∑_{y∈Y}⟨f^{y}, g⟩| ≤ ∑_{z∈V̄′′_{3}} |ξ_{z}g_{z}| ≤ \frac{8ε̄}{β_{2}}ω ∑_{z∈V̄′′_{3}} |g_{z}|.

We have from our assumptions on our constants that ρ̄ ≤ ε̄/β_{2} ≤ β_{1}/27 ≤ 1/27. Hence

∑_{z∈V̄′′_{3}} |g_{z}| ≤ ∑_{z∈V̄_{3}} |g_{z}| ≤ (1 + ρ̄)d_{13} + d_{13} ≤ \frac{9}{4}d_{13},

with plenty to spare. Thus

| ∑_{y∈Y}⟨f^{y}, g⟩| ≤ \frac{18ε̄}{β_{2}}ωd_{13}.  (7)

We now give a lower estimate for the left-hand side of (7) in terms of the σ(x, y) (y ∈ Y). Let d′′_{13}(x) = |Γ_{F_{13}}(x) ∩ V̄′′_{3}| and recall that we let d′′_{23}(y) = |Γ_{F_{23}}(y) ∩ V̄′′_{3}| for all y ∈ Y. Put m′′_{3} = |V̄′′_{3}| and d′′(x, y) = |Γ_{F_{13}}(x) ∩ Γ_{F_{23}}(y) ∩ V̄′′_{3}| for all y ∈ Y. Fix y ∈ Y. Clearly d′′(x, y) ≤ d(x, y) = |Γ_{F_{13}}(x) ∩ Γ_{F_{23}}(y)|. Thus

\begin{aligned}⟨f^{y}, g⟩ = d′′(x, y) − \frac{d_{13}}{m_{3}} & \{d′′_{23}(y) − d′′(x, y)\} − \frac{d_{23}}{m_{3}} \{d′′_{13}(x) − d′′(x, y)\} \\ & + \frac{d_{13}d_{23}}{m_{3}^{2}} (m′′_{3} − \{d′′_{13}(x) + d′′_{23}(y) − d′′(x, y)\}). \end{aligned}

Write d′′_{13}(x) = (1 − τ)d_{13}. Recalling (6), we see that

⟨f^{y}, g⟩ ≤ d(x, y) − 2\frac{d_{13}d_{23}}{m_{3}} + \frac{d_{13}d_{23}m′′_{3}}{m_{3}^{2}}

+ \frac{3ε̄d_{13}d_{23}}{β_{2}m_{3}} + τ \frac{d_{13}d_{23}}{m_{3}} + \frac{d_{13}d′′(x, y)}{m_{3}} + \frac{d_{23}d′′(x, y)}{m_{3}}

− \frac{d_{13}d_{23}d′′_{13}(x)}{m_{3}^{2}} − \frac{d_{13}d_{23}d′′_{23}(y)}{m_{3}^{2}} + \frac{d_{13}d_{23}d′′(x, y)}{m_{3}^{2}}

≤ σ(x, y) + \frac{3ε̄d_{13}d_{23}}{β_{2}m_{3}} + τ \frac{d_{13}d_{23}}{m_{3}} + \frac{d_{13} + d_{23}}{m_{3}} d′′(x, y) + o (\frac{d_{13}d_{23}}{m_{3}} ) ,

where we used that, trivially, m′′_{3} ≤ m_{3}, and that d_{13}(x), d_{23}(y), and d′′(x, y) are all o(m_{3}), since by assumption p = p(m) → 0 as m → ∞. However,

\frac{d_{13} + d_{23}}{m_{3}} ∑_{y∈Y} d′′(x, y) = \frac{d_{13} + d_{23}}{m_{3}} ∑_{y∈Y} |Γ_{F_{13}}(x) ∩ Γ_{F_{23}}(y) ∩ V̄′′_{3}|

≤ \frac{d_{13} + d_{23}}{m_{3}} ∑ \{d^{Y} (z): z ∈ Γ_{F_{13}}(x) ∩ V̄′′_{3}\}

≤ \frac{d_{13} + d_{23}}{m_{3}} (1 + ρ̄) (1 + \frac{4ε̄}{β_{2}}) ωd_{13},

which is o(d_{13}d_{23}q/m_{3}). Therefore

∑_{y∈Y}⟨f^{y}, g⟩ ≤ − (β_{1} − \frac{4ε̄}{β_{2}} − τ) \frac{d_{13}d_{23}q}{m_{3}} .  (8)

Using that q = (1 + O_{1}(3ε̄/β_{2}))ωm_{2}/d_{32} and that d_{23}/m_{3} = d_{32}/m_{2}, we deduce from inequality (8) above that

∑_{y∈Y}⟨f^{y}, g⟩ ≤ − (β_{1} − \frac{4ε̄}{β_{2}} − τ) (1 + O_{1} (\frac{3ε̄}{β_{2}})) ωd_{13}

≤ − (β_{1} − \frac{4ε̄}{β_{2}} − τ + O_{1} (\frac{3ε̄}{β_{2}})) ωd_{13}.  (9)

We now claim that τ ≥ 2ε̄/β_{2}. Indeed, otherwise we would have that β_{1} − 4ε̄/β_{2} − τ + O_{1}(3ε̄/β_{2}) ≥ 0, and hence, comparing inequalities (7) and (9), we would have that β_{1} − 4ε̄/β_{2} − τ + O_{1}(3ε̄/β_{2}) ≤ 18ε̄/β_{2}, and consequently that τ ≥ 2ε̄/β_{2}, which is a contradiction.

Recall that d′′_{13}(x) = |Γ_{F_{13}}(x) ∩ V̄′′_{3}| = (1 − τ)d_{13} and that d_{13}(x) = |Γ_{F_{13}}(x)| = (1 + O_{1}(ρ̄))d_{13}. Also, |V̄_{3} \ V̄′′_{3}| ≤ 2ε̄|V̄_{3}|. Thus we deduce from the existence of the set Y that at least (τ − ρ̄)d_{13} ≥ τd_{13}/2 elements of Γ_{F_{13}}(x) ⊂ V̄_{3} are confined to a subset of V̄_{3} of cardinality at most 2ε̄|V̄_{3}|. Thus, by Lemma 6, the probability that such a set Y exists is at most 2^{(1+ρ̄)d_{13}}(3ε̄)^{τd_{13}/2} ≤ 2^{3d_{13}/2}(3ε̄)^{ε̄d_{13}/β_{2}} ≤ (4ε̄^{ε̄/β_{2}})^{d_{13}}, completing the proof of Assertion 3.

We may now finish the proof of Lemma 8 combining Assertions 2 and 3 above. Indeed, writing ∑′_{q} for the sum over all q satisfying q = (1 + O_{1}(3ε̄/β_{2}))ωm_{2}/d_{32}, we have from the above two assertions that probability that the vertex x should be (β_{1}, β_{2})-faulty is, for large enough m, at most

\begin{matrix}(4ε̄^{ε̄/β_{2}})^{d_{13}} ∑′_{q} \binom{m_{2}}{q} ≤ \frac{6ε̄ωm_{2}}{β_{2}d_{32}} \binom{m_{2}}{2ωm_{2}/d_{32}}(4ε̄^{ε̄/β_{2}})^{d_{13}} \\ ≤ \frac{6ε̄ωm_{2}}{β_{2}d_{32}} (\frac{ed_{32}}{2ω} )^{2ωm_{2}/d_{32}} (4ε̄^{ε̄/β_{2}})^{d_{13}} ≤ (5ε̄^{ε̄/β_{2}})^{d_{13}}, \end{matrix}

where in the last inequality we used that ωm_{2}(log m)/d_{32} = o(d_{13}), which follows easily from our assumption that pm ≥ m^{1/2+1/ log log log m} for all sufficiently large m. Thus Lemma 8 is proved. □

We are now in position to finish the proof of Lemma 7.

Proof of Lemma 7. Let us first state a simple fact concerning the T_{i}. Assertion 1. For all i ∈ {1, 2, 3} we have T_{i} ≥ (γ̄_{0}/24)T. Indeed, T ≤ ∑_{i∈{1,2,3}} γ_{i}pm_{i−1}m_{i+1} ≤ 6pm^{2}, and therefore, for any i ∈ {1, 2, 3}, we have

T_{i} = γ_{i}pm_{i−1}m_{i+1} ≥ \frac{γ̄_{0}}{4} pm^{2} ≥ \frac{γ̄_{0}}{24}T,

as required.

Our next observation is an immediate consequence of Lemma 8 and Assertion 1.

Assertion 2. Let 0 < β_{3} ≤ 1 be given. The probability that at least β_{3}m_{1} vertices in V̄_{1} are (β_{1}, β_{2})-faulty is at most (6ε̄^{ε̄/β_{2}})^{β_{3}γ̄_{0}T/24}.

Indeed, by Lemma 8 and Assertion 1 above, the probability in question is at most

2^{m_{1}}((5ε̄^{ε̄/β_{2}})^{d_{13}})^{β_{3}m_{1}} = 2^{m_{1}}(5ε̄^{ε̄/β_{2}})^{β_{3}T_{1}} ≤ (6ε̄^{ε̄/β_{2}})^{β_{3}γ̄_{0}T/24},

completing the proof of Assertion 2.

We now describe the last step in the generation of F. Recall that we have generated F_{13} ∪ F_{23} = F [V̄_{1}, V̄_{3}] ∪ F [V̄_{2}, V̄_{3}] so far. Let K[V̄_{1}, V̄_{2}] be the complete bipartite graph with bipartition V̄_{1} ∪ V̄_{2}. To generate F_{12} = F [V̄_{1}, V̄_{2}], we randomly pick for E(F [V̄_{1}, V̄_{2}]) a T_{3}-element subset of E(K[V̄_{1}, V̄_{2}]), uniformly chosen from all such sets.

Assertion 3. Suppose that fewer than β_{3}m_{1} vertices in V̄_{1} are (β_{1}, β_{2})-faulty. Then the probability that at least δT_{3} edges in F_{12} = F [V̄_{1}, V̄_{2}] are (β_{1}, K^{3})-poor is no larger than {4(β_{2} + β_{3})^{δγ̄_{0}/24}}^{T}.

Recall that an edge xy ∈ E(F [V̄_{1}, V̄_{2}]) (x ∈ V̄_{1}, y ∈ V̄_{2}) is (β_{1}, K^{3})-poor if and only if y ∈ Ṽ_{2}(x, β_{1}). The probability in question P_{0} is the probability that at least δT_{3} edges xy ∈ E(K[V̄_{1}, V̄_{2}]) (x ∈ V̄_{1}, y ∈ V̄_{2}) with y ∈ Ṽ_{2}(x, β_{1}) are selected to be elements of F_{12}. The number of such ‘potentially poor’ edges xy in K[V̄_{1}, V̄_{2}] is at most β_{3}m_{1}m_{2} + (1 − β_{3})β_{2}m_{1}m_{2} ≤ (β_{2} + β_{3})m_{1}m_{2}, and hence, by Lemma 6 and Assertion 1, we have

P_{0} ≤ 2^{T_{3}}{2(β_{2} + β_{3})}^{δT_{3}} ≤ {4(β_{2} + β_{3})^{δ}}^{γ̄_{0}T/24} ≤ {4(β_{2} + β_{3})^{δγ̄_{0}/24}}^{T} ,

proving Assertion 3.

We may now finish the proof of Lemma 7. Let the constants α, γ̄_{0}, and δ as in the statement of our lemma be given. We then let ε_{0} = ε_{0}(α, γ̄_{0}, δ) be such that 0 < ε_{0} ≤ δγ̄_{0}/27 and, moreover,

(6ε̄^{δ/27})^{γ̄_{0}/24 log log(1/ε̄)} ≤ \frac{1}{6}α

and

4 (\frac{27ε̄}{δ} + \frac{1}{log log(1/ε̄)})^{δγ̄_{0}/24} ≤ \frac{1}{6}α

for all 0 < ε̄ ≤ ε_{0}.

We now apply Assertions 2 and 3 above with suitably chosen β_{1}, β_{2}, β_{3}, ε̄, and ρ̄. Let β_{1} = δ and fix any 0 < ε̄ ≤ ε_{0}. Let β_{2} = 27ε̄/δ ≤ γ̄_{0} and β_{3} = 1/ log log(1/ε̄). Recall that ρ̄_{0} = δ/27. To complete the proof, we proceed as follows: we suppose that ρ̄ ≤ ρ̄_{0} is given and that m is sufficiently large for the inequalities below to hold. Fix the partition T = T_{1} + T_{2} + T_{3} of T, the bipartite graph F_{23} = F [V̄_{2}, V̄_{3}], and the degree sequence (d_{13}(x))_{x∈V̄_{1}} as above. Then generate F_{13} = F [V̄_{1}, V̄_{3}]. The probability that at least β_{3}m_{1} vertices in V̄_{1} are (β_{1}, β_{2})-faulty is, by Assertion 2, at most

(6ε̄^{ε̄/β_{2}})^{β_{3}γ̄_{0}T/24} = (6ε̄^{δ/27})^{β_{3}γ̄_{0}T/24} ≤ (\frac{α}{6})^{T} ≤ \frac{1}{6}α^{T} .

Let us now assume that fewer than β_{3}m_{1} vertices in V̄_{1} are (β_{1}, β_{2})-faulty, and let us generate F_{12} = F [V̄_{1}, V̄_{2}]. Then the probability that δT_{3} edges in F_{12} = F [V̄_{1}, V̄_{2}] are (δ, K^{3})-poor is, by Assertion 3, at most

\{4(β_{2} + β_{3})^{δγ̄_{0}/24}\}^{T} ≤ \{4 (\frac{27ε̄}{δ} + \frac{1}{log log(1/ε̄)})^{δγ̄_{0}/24}\}^{T} ≤ (\frac{α}{6})^{T} ≤ \frac{1}{6}α^{T} .

We now note that the argument above is symmetric with respect to the indices i ∈ {1, 2, 3} (note the factor ‘3’ below), and thus we may conclude that

|F_{p}^{δ}(ε̄, γ̄_{0}, ρ̄; V, T)| ≤ 3 × \frac{2}{6}α^{T} \binom{3m^{2}}{T} ≤ α^{T} \binom{3m^{2}}{T},

completing the proof of Lemma 7. □

Recall that m and T are integers, 0 < ε̄ ≤ 1, 0 < γ̄_{0} ≤ 1, 0 < δ ≤ 1, and 0 < ρ̄ ≤ 1 are fixed reals, 0 < p = p(m) ≤ 1 is such that pm → ∞ and p = o(1) as m → ∞, and V = (V̄_{1}, V̄_{2}, V̄_{3}) and m = (m_{1}, m_{2}, m_{3}), where the V̄_{i} (i ∈ {1, 2, 3}) are pairwise disjoint sets with cardinality |V̄_{i}| = m_{i} (i ∈ {1, 2, 3}). Our next lemma concerns a property of graphs F ∈ F_{p}(ε̄, γ̄_{0}, ρ̄, T)\F_{p}^{δ}(ε̄, γ̄_{0}, ρ̄, T), namely, graphs F in F_{p}(ε̄, γ̄_{0}, ρ̄, T) that are (δ, K^{3})-balanced. For a vertex x ∈ V (F), let k_{3}(x) = k_{3}^{F} (x) denote the number of triangles of F that contain x.

Lemma 9. Suppose F is a (δ, K^{3})-balanced graph in F_{p}(ε̄, γ̄_{0}, ρ̄; V, T). Put δ′ = (2δ)^{1/2}. Then, for any i ∈ {1, 2, 3}, there are at most δ′m_{i} vertices x in V̄_{i} such that

k_{3}(x) = k_{3}^{F} (x) < (1 − ρ̄ − δ′)γ_{1}γ_{2}γ_{3}p^{3}m_{i−1}m_{i+1}.

Proof. By symmetry, it suffices to prove the statement for i = 1. In the sequel we freely use the notation introduced before Lemma 7. Also, let us put d_{ij} = Ave_{x∈V̄_{i}} d_{ij}(x) = γ_{k}pm_{j} for all i, j, and k with {i, j, k} = [3]. Below we say that a vertex x ∈ V̄_{1} is bad if at least δd_{12}/δ′ = δ′d_{12}/2 edges in E(F [V̄_{1}, V̄_{2}]) incident to x are (δ, K^{3})-poor edges. The number of such bad vertices x ∈ V̄_{1} is at most δ′m_{1}, as otherwise the number of (δ, K^{3})-poor edges in E(F [V̄_{1}, V̄_{2}]) would be more than δm_{1}d_{12} = δe(F [V̄_{1}, V̄_{2}]), contradicting the fact that F is (δ, K^{3})- balanced.

Note that an edge e = x_{1}x_{2} ∈ E(F [V̄_{1}, V̄_{2}]) (x_{i} ∈ V̄_{i}, i ∈ {1, 2}) that is not (δ, K^{3})-poor ‘contributes’ with at least k_{3}(e) ≥ (1 − δ)γ_{1}γ_{2}p^{2}m_{3} triangles to k_{3}(x_{1}). Supposing that x_{1} ∈ V̄_{1} is not a bad vertex, summing over all x_{2} ∈ V̄_{2} for which x_{1}x_{2} ∈ E(F [V̄_{1}, V̄_{2}]) is not a (δ, K^{3})-poor edge, we obtain that

k_{3}(x_{1}) ≥ ((1 − ρ̄)d_{12} − \frac{δ′}{2} d_{12}) (1 − δ)γ_{1}γ_{2}p^{2}m_{3}

≥ (1 − ρ̄ − δ − \frac{δ′}{2} ) γ_{1}γ_{2}γ_{3}p^{3}m_{2}m_{3} ≥ (1 − ρ̄ − δ′)γ_{1}γ_{2}γ_{3}p^{3}m_{2}m_{3}.

Since, as we saw above, at most δ′m_{1} vertices x_{1} ∈ V̄_{1} are bad, the proof is complete. □

2.2. Distribution of triangles in random graphs. In this section we look at the random graph G_{p} = G_{n,p} and study the distribution of the triangles it contains. The aim will be to prove that the triangles of G_{n,p} do not unduly concentrate on any fixed set of edges and vertices. To be precise, let x be any given vertex of G_{p} and let E be a set of edges of G_{p} taken from the subgraph G_{p}[Γ_{G_{p}}(x)] induced by the neighbourhood Γ_{G_{p}}(x) of x in G_{p}. Also, let W be a subset of vertices of G_{p} disjoint from {x}∪V (E), where we write V (E) for the set V (G_{p}[E]) of vertices of G_{p} that are incident to at least one edge from E. Our aim is to find an upper bound for the number of triangles k_{3}(E, W) = k_{3}^{G_{p}}(E, W) of G_{p} that are determined by an edge from E and a vertex in W. Note that the expected value of this number is p^{2}|E||W |. We shall show that this is an upper bound in probability up to 1 + θ for any fixed θ > 0 as long as E and W are reasonably large and p = p(n) does not tend to 0 too fast.

Lemma 10. Let c_{1}, c_{2} > 0 and 0 < θ ≤ 1 be given. Then there is a constant C_{0} = C_{0}(c_{1}, c_{2}, θ) that depends only on c_{1}, c_{2}, and θ for which the following holds. Suppose p = p(n) = ωn^{−2/5} where C_{0} ≤ ω = ω(n) = o(n^{1/190}). Then almost every G_{p} = G_{n,p} is such that, if E ⊂ E(G_{p}[Γ_{G_{p}}(x)]) and W ⊂ W̃ = V (G_{p}) \ ({x} ∪ V (E)) for some x ∈ V (G_{p}), then

k_{3}(E, W) = k_{3}^{G_{p}}(E, W) ≤ (1 + θ)p^{2}|E||W |  (10)

as long as |E| ≥ c_{1}p^{3}n^{2} and |W | ≥ c_{2}n.

Most of the remainder of this section is devoted to the proof of Lemma 10. Unfortunately, our proof below is a little indirect and is based on a few auxiliary lemmas; moreover, this proof makes use of a technical condition that ω should not be too large. The obvious direct approaches based on simple large deviation inequalities seem to fail to give Lemma 10. To see why this might be expected, note that (i) for the sets E and W of interest, the expected value 𝔼(k_{3}(E, W)) = p^{2}|E||W | of k_{3}(E, W) is of order O(n) only, while the number of sets W that we have to handle is exp{Ω(n)}, and (ii) k_{3}(E, W) is a sum of positively correlated indicator variables and the most common large deviation inequalities for such sums do not seem to be strong enough for our purposes.

Let us turn to the proof of Lemma 10. For the rest of this section we assume that p = p(n) = ωn^{−2/5}, where C_{0} ≤ ω = ω(n) = o(n^{1/190}) and C_{0} is some large constant. (The main result for G_{p} with larger p will be deduced from the small p case; cf. Lemma 19.)

Let P^{3} be the path of length 2 and E^{k} the k-vertex graph with no edges (k ≥ 1). We write H_{k} for P^{3} ∨ E^{k} (k ≥ 1), the graph on k + 3 vertices we obtain from the disjoint union of P^{3} and E^{k} by adding all the 3k edges between V (P^{3}) and V (E^{k}). A little piece of arithmetic shows that almost no G_{n,p} contains a copy of H_{12}. Thus for the rest of this section we may and shall assume that our G_{n,p} is H_{12}-free.

We may clearly assume that the degree of any vertex of G_{p} = G_{n,p} is (1 + o(1))pn, and also that any vertex of G_{p} is contained in at most p^{3}n^{2} triangles. Furthermore, the expected number of common neighbours of any two fixed vertices of G_{p} is p^{2}(n−2) ≤ ω^{2}n^{1/5}. Thus, we may and shall condition on our G_{p} being such that d_{G_{p}}(x, y) = |Γ_{G_{p}}(x) ∩ Γ_{G_{p}}(y)| ≤ 2ω^{2}n^{1/5} for any pair of distinct vertices x, y ∈ V (G_{p}). Finally, we may assume that G_{p} is o(1)-upper-uniform.

Suppose x ∈ V (G_{p}) and E ⊂ E(G_{p}[Γ_{G_{p}}(x)]). For a vertex y ∈ W̃ = V (G_{p}) \ ({x} ∪ V (E)), let E_{y} be the set E ∩ E(G_{p}[Γ_{G_{p}}(y)]) of edges of E that the neighbourhood of y in G_{p} induces in G_{p}. Clearly, k_{3}(E, y) = k_{3}(E, {y}) = |E_{y}|. We shall say that a vertex y ∈ W̃ is (x, E)-bad, or simply E-bad, if E_{y} is not an independent set of edges.

Lemma 11. Almost every G_{p} is such that, for any x ∈ V (G_{p}) and any E ⊂ E(G_{p}[Γ_{G_{p}}(x)]), at most 10eω^{8}n^{4/5} vertices are E-bad.

Proof. Fix a vertex x ∈ V (G_{p}). Let us generate G_{p} as follows: we first choose the neighbourhood Γ_{G_{p}}(x) of x in G_{p}, and once this set is fixed, we decide which edges within Γ_{G_{p}}(x) should be in G_{p}. Put E^{(0)} = E(G_{p}[Γ_{G_{p}}(x)]), and let V (E^{(0)}) ⊂ Γ_{G_{p}}(x) be the set of vertices in Γ_{G_{p}}(x) that are incident to at least one edge in E(G_{p}[Γ_{G_{p}}(x)]). For the rest of the proof, we assume that the edges generated so far are fixed.

Let us now consider a vertex y ∈ Y = V (G_{p}) \ ({x} ∪ Γ_{G_{p}}(x)), and let us decide which edges between y and V (E^{(0)}) should be in our G_{p}. Notice that whether or not y is E^{(0)}-bad depends solely on these y–V (E^{(0)}) edges. In particular, the events ‘y is E^{(0)}-bad’ (y ∈ Y) are all independent. Let us estimate the probability that a given vertex y ∈ Y turns out to be E^{(0)}-bad. We first observe that with probability 1 − o(1/n) we have |V (E^{(0)})| ≤ |Γ_{G_{p}}(x)| ≤ 2pn and |Δ(E^{(0)})| = |Δ(G_{p}[E^{(0)}])| ≤ 2p^{2}n = 2ω^{2}n^{1/5}. In the sequel, we assume that these two inequalities hold. In particular, the number of copies of P^{3} spanned by E^{(0)} is, crudely, at most |V (E^{(0)})|Δ(E^{(0)})^{2} ≤ 8ω^{5}n. Thus the probability that y is E^{(0)}-bad is

ℙ(Δ(E_{y}^{(0)}) ≥ 2) = ℙ(G_{p}[E_{y}^{(0)}] contains a P^{3})
≤ 𝔼(#{P^{3} ⊂ G_{p}[E_{y}^{(0)}]}) ≤ 8ω^{5}np^{3} = 8ω^{8}n^{−1/5},

where #{P^{3} ⊂ G_{p}[E_{y}^{(0)}]} denotes the number of copies of P^{3} in G_{p}[E_{y}^{(0)}]. Now, from the independence of the events ‘y is E^{(0)}-bad’ (y ∈ Y), we have that the probability P_{k} that at least k such vertices y are E^{(0)}-bad satisfies

P_{k} ≤ \binom{n}{k}\{8ω^{8}n^{−1/5}\}^{k} ≤ (\frac{8eω^{8}n^{4/5}}{k} )^{k} .  (11)

Thus, if k = ⌊9eω^{8}n^{4/5}⌋, we have P_{k} = o(1/n) with plenty to spare.

The above argument proves our lemma with ‘E ⊂ E(G_{p}[Γ_{G_{p}}(x)])’ replaced by ‘E = E(G_{p}[Γ_{G_{p}}(x)])’. To complete the proof, we make the following simple observation. Suppose x ∈ V (G_{p}) is fixed, E ⊂ E^{(0)} = E(G_{p}[Γ_{G_{p}}(x)]), and y ∈ Y = V (G_{p}) \ ({x} ∪ Γ_{G_{p}}(x)). Then, y is necessarily E^{(0)}-bad whenever it is E-bad. Thus, an E-bad vertex y ∈ W̃ = V (G_{p})\(V (E)∪{x}) is either contained in Γ_{G_{p}}(x) or else it is E^{(0)}-bad. Since we may assume that Δ(G_{p}) ≤ 2pn = 2ωn^{3/5} ≤ ω^{8}n^{4/5}, our lemma follows. □

Lemma 11 above tells us that, for any x and any E, we have Δ(E_{y}) = Δ(G_{p}[E_{y}]) ≤ 1 for most y ∈ W̃ = V (G_{p}) \ ({x} ∪ V (E)). Of course, since G_{p} is supposed not to contain H_{12}, we have Δ(E_{y}) ≤ 11 for any vertex y ∈ W̃.

For each vertex y ∈ W̃, let X_{y} = |E_{y}| = k_{3}(E, y) and let X′_{y} be the cardinality ν(E_{y}) = ν(G_{p}[E_{y}]) of a maximum matching in G_{p}[E_{y}]. Since Δ(E_{y}) ≤ 11, we have X′_{y} ≥ X_{y}/2Δ(E_{y}) ≥ X_{y}/22 for any y ∈ W̃. Moreover, for any y ∈ W̃ that is not E-bad, we clearly have X′_{y} = X_{y}.

Let us now fix W ⊂ W̃. Put

X = X_{W} = ∑_{w∈W} X_{w} = ∑_{w∈W} k_{3}(E, w) = k_{3}(E, W),

and similarly X′ = X′_{W} = ∑_{w∈W} X′_{w}. Let us write ∑_{b} for sum over all w ∈ W that are E-bad and ∑_{g} for sum over all w ∈ W that are not E-bad. Then

k_{3}(E, W) = X_{W} = ∑_{g} X_{w} + ∑_{b} X_{w}
= ∑_{g} X′_{w} + ∑_{b} X_{w} ≤ X′_{W} + ∑_{b} X_{w}.  (12)

Now our aim is to bound the last two summands in (12).

For any two distinct vertices x and y ∈ V (G_{p}), let Y_{xy} be the number of edges induced by the set Γ_{G_{p}}(x, y) = Γ_{G_{p}}(x)∩Γ_{G_{p}}(y) in G_{p}. Thus Y_{xy} = |E(G_{p}[Γ_{G_{p}}(x, y)])|, and 𝔼(Y_{xy}) = \binom{n−2}{2}p^{5} = (1/2 + o(1))ω^{5}.

Lemma 12. For almost every G_{p} we have Y_{xy} ≤ 22e^{2} max{log n, ω^{5}} for any pair of distinct vertices x, y ∈ V (G_{p}).

Proof. Let Y′_{xy} be the maximum cardinality ν(G_{p}[Γ_{G_{p}}(x, y)]) of a matching in G_{p}[Γ_{G_{p}}(x, y)]. We claim that

ℙ{Y′_{xy} ≥ e^{2} max{log n, ω^{5}}} ≤ n^{−e^{2}} = o(n^{−2}).  (13)

For convenience, put μ = 𝔼(Y_{xy}) ≤ ω^{5}. By Lemma 2 in Janson [10], for any a ≥ e^{2}, we have

ℙ(Y′_{xy} ≥ aμ) ≤ exp\{−μ(a log a + 1 − a)\} ≤ exp \{−\frac{1}{2}a(log a)μ\} .  (14)

We now check that (13) follows from (14). Suppose μ = 𝔼(Y_{xy}) ≤ log n. Then we take a = e^{2}μ^{−1} log n ≥ e^{2} in (14) and note that then

ℙ(Y′_{xy} ≥ e^{2} log n) = ℙ(Y′_{xy} ≥ aμ) ≤ exp{−e^{2} log n} = n^{−e^{2}}.

Suppose now that μ = 𝔼(Y_{xy}) > log n. Then we take a = e^{2} in (14) to obtain

ℙ(Y′_{xy} ≥ e^{2}ω^{5}) ≤ ℙ(Y′_{xy} ≥ e^{2}μ) ≤ exp{−e^{2} log n} = n^{−e^{2}}.

Thus the claimed inequality (13) does hold. In particular, almost surely Y′_{xy} ≤ e^{2} max{log n, ω^{5}} for any distinct x, y ∈ V (G_{p}). Our lemma now follows, since Δ(G_{p}[Γ_{G_{p}}(x, y)]) ≤ 11, and hence Y′_{xy} ≥ Y_{xy}/22. □

By Lemmas 11 and 12 above, an almost sure upper bound for the last summand in (12) is 220e^{3} max{log n, ω^{5}}ω^{8}n^{4/5}. Our aim now is to estimate X′_{W}. Fortunately, the method of proof of Lemma 2 in Janson [10] gives the following result immediately.

Lemma 13. Suppose 0 ≤ ε ≤ 1/2. Then for any W ⊂ W̃ = V (G_{p}) \ ({x} ∪ V (E)) we have

ℙ(X′_{W} ≥ (1 + ε)p^{2}|E||W |) ≤ exp \{−\frac{1}{3}ε^{2}p^{2}|E||W |\} .

Proof. We follow an argument of Janson [10] (cf. the proof of Lemma 2 in [10]). Fix W ⊂ W̃ = V (G_{p}) \ ({x} ∪ V (E)) and let w ∈ W. Let F be the family of all copies J of P^{3} with middle vertex w and endvertices coinciding with endvertices of edges in E in the complete graph on V (G_{p}). Thus each such J corresponds to a triangle determined by w and one edge from E. Let F_{m} (m ≥ 0) be the collection of all m-tuples (J_{1}, …, J_{m}) of pairwise edge-disjoint elements from F. Let I_{J} be the indicator variable of the event that a fixed J ∈ F should be present in G_{p}. Thus k_{3}(E, w) = X_{w} = ∑_{J∈F} I_{J}. We have

\begin{matrix}𝔼(e^{tX′_{w}}) = 𝔼\{ ∑_{m≥0} \binom{X′_{w}}{m}(e^{t} − 1)^{m}\} ≤ 𝔼\{ ∑_{m≥0} \frac{1}{m!} ∑_{F_{m}} I_{J_{1}} … I_{J_{m}} (e^{t} − 1)^{m} \} \\ = ∑_{m≥0} \frac{1}{m!} ∑_{F_{m}} p^{2m} (e^{t} − 1)^{m} ≤ ∑_{m≥0} \frac{1}{m!}\{ ∑_{F} p^{2} (e^{t} − 1) \}^{m} = e^{λ(e^{t}−1)}, \end{matrix}

where λ = 𝔼(X_{w}). Now, the X′_{w} (w ∈ W) are independent and therefore

𝔼(e^{tX′_{W}}) = 𝔼(e^{t ∑_{w∈W} X′_{w}}) = ∏_{w∈W} 𝔼(e^{tX′_{w}}) ≤ e^{λ|W |(e^{t}−1)}.

Let a ≥ 1. Note that then, by Markov’s inequality, we have

ℙ(X′_{W} ≥ aλ|W |) = ℙ(e^{tX′_{W}} ≥ e^{taλ|W |})
≤ 𝔼(e^{tX′_{W}})e^{−taλ|W |} ≤ e^{λ|W |(e^{t}−1)}e^{−taλ|W |} = e^{λ|W |(e^{t}−1−at)}.

Taking t = log a, we have

ℙ(X′_{W} ≥ aλ|W |) ≤ e^{λ|W |(a−1−a log a)} = e^{−λ|W |(a log a−a+1)}.

Our lemma follows by setting a = 1 + ε in this last inequality. □

We are finally ready to prove Lemma 10.

Proof of Lemma 10. Take C_{0} = C_{0}(c_{1}, c_{2}, θ) = {12/(θ^{2}c_{1}c_{2})}^{1/5}. We proceed to show that this choice for C_{0} will do. Thus let x, E, and W as in the statement of our lemma be given. To prove (10), it suffices to put together (12) and Lemmas 11, 12, and 13. Indeed, with the notation as above, by Lemma 13 we have

ℙ (X′_{W} ≥ (1 + \frac{θ}{2}) p^{2}|E||W |) ≤ exp \{−\frac{1}{3} (\frac{θ}{2})^{2} p^{2}|E||W |\} ≤ e^{−n},

where in the last inequality we used that |E| ≥ c_{1}p^{3}n^{2}, |W | ≥ c_{2}n, and C_{0} = {12/(θ^{2}c_{1}c_{2})}^{1/5}.

The number of choices for the triple (x, E, W) is at most n exp{2ω^{3}n^{4/5} log n}2^{n}. Indeed, it suffices to notice that we may assume that |E| ≤ u_{0} = ⌊p^{3}n^{2}⌋ = ⌊ω^{3}n^{4/5}⌋, and hence the number of choices for E is at most

∑_{u≤u_{0}} \binom{n^{2}}{u} ≤ 2\binom{n^{2}}{u_{0}} ≤ exp\{2ω^{3}n^{4/5} log n\}.

Thus almost every G_{p} is such that X′_{W} ≤ (1 + θ/2)p^{2}|E||W |.

From (12) and Lemmas 11 and 12, we have, for almost every G_{p},

k_{3}(E, W) ≤ (1 + \frac{θ}{2}) p^{2}|E||W | + 220e^{3} max\{log n, ω^{5}\}ω^{8}n^{4/5},

which is at most (1 + θ)p^{2}|E||W |, as required. □

In our next lemma we give a set of conditions that ensures that k_{3}^{G_{p}}(E, W) (E ⊂ E(G_{p}), W ⊂ V (G_{p}) \ V (E)) concentrates around its mean.

Lemma 14. Suppose ω = ω(n) → ∞ as n → ∞. Let 0 < p = p(n) ≤ 1 with p ≥ ωn^{−1/2} log n be given. Then almost every G_{p} = G_{n,p} is such that, for any E ⊂ E(G_{p}) and W ⊂ V (G_{p}) \ V (E) with |E| ≥ ωnp^{−1} log n and |W | ≥ n/ log n, we have

k_{3}(E, W) = k_{3}^{G_{p}}(E, W) = (1 + o(1))p^{2}|E||W |.  (15)

Proof. Let θ > 0 be fixed. Let M ⊂ E(K^{n}) be a matching in the complete graph K^{n}, and set ν = |M|. Suppose that νp^{2}/ log n → ∞ as n → ∞. Let W ⊂ V (G_{p}) \ V (M) be such that w = |W | ≥ n/ log n. Let us write k′_{3}(M, W) = k_{3}^{G_{p}∪M}(M, W) for the number of triangles in G_{p} ∪ M that are determined by an edge of M and a vertex of W. Note that k′_{3}(M, W) has binomial distribution with parameters νw = |M||W | and p^{2}. Thus

k′_{3}(M, W) = (1 + O_{1}(θ))p^{2}|M||W |  (16)

with probability 1 − exp{−Ω(p^{2}νw)}. The number of matchings M ⊂ E(K^{n}) of cardinality ν is no larger than \binom{\binom{n}{2}}{ν} ≤ n^{2ν}, and the number of sets W as above is no larger than \binom{n}{w} ≤ n^{w}. Hence, we see that (16) holds a.s. for any matching M ⊂ E(K^{n}) with |M| ≥ ν_{0} = ω(log n)/4p^{2} and any W ⊂ V (G_{p}) \ V (M) with |W | ≥ n/ log n, since

∑_{ν≥ν_{0}} ∑_{w≥n log n} n^{2ν+w} exp{−p^{2}νw} ≤ ∑_{ν≥ν_{0}} n^{2ν} ∑_{w≥n log n} (ne^{−Ω(p^{2}ν)})^{w}

≤ ∑_{ν≥ν_{0}} n^{2ν−Ω(p^{2}νn/ log n)}

= o(1).

Thus, let us assume that our G_{p} does have this property. Clearly, we may also assume that Δ(G_{p}) ≤ 2pn. We claim that under these assumptions our G_{p} necessarily satisfies (15) with ‘o(1)’ replaced by ‘O_{1}(θ)’ for all E and W as in the statement of our lemma. To see this, fix E ⊂ E(G_{p}) and W ⊂ V (G_{p}) \ V (E) as in the lemma.

We shall now make use of the following simple fact that may be easily deduced from Vizing’s theorem: if J is a graph of maximum degree Δ(J), then J admits a proper edge-colouring with at most Δ(J) + 1 colours such that the cardinality of any two colour classes differ by at most 1. Note that Δ(E) = Δ(G_{p}[E]) ≤ Δ(G_{p}) ≤ 2pn, and hence, by the observation above, we may write E = E_{1} ∪ ⋯ ∪ E_{q} where the E_{i} are matchings satisfying ||E_{i}| − |E_{j}|| ≤ 1 for all i and j, and moreover q ≤ Δ(E) + 1 ≤ 3pn. In particular, |E_{i}| ≥ |E|/4pn ≥ ν_{0} for all i. Therefore (16) applies with M = E_{i} and, since k_{3}(E, W) = ∑_{1≤i≤q} k_{3}(E_{i}, W), our claim does hold. Lemma 14 follows by letting θ tend to 0. □

§3. Pivotal Pairs of Vertices

3.1. A weighted Turán type result. Let H_{∗} be a graph and r ≥ 3 an integer. Let us write K_{−}^{r} for the graph with r vertices and \binom{r}{2} − 1 edges, and let us say that its two vertices of degree r − 2 are the endvertices of K_{−}^{r}. Let us say that the unordered pair xy = {x, y} of distinct vertices of H_{∗} is a K_{−}^{r}-connected pair if there is a copy of K_{−}^{r} in H_{∗} with endvertices x and y. Hence, if xy is a K_{−}^{r}-connected pair of non-adjacent vertices, then the addition of xy to H_{∗} creates a new copy of K^{r} in H_{∗}. Thus, we shall also say that a K_{−}^{r}-connected pair is K^{r}-pivotal, or simply pivotal. For technical reasons, let us also say that the vertex x ∈ V (H_{∗}) is by itself a K_{−}^{r}-connected pair if x lies in a copy of K^{r−1} in H_{∗}. The following is an asymptotic version of Turán’s theorem for K^{r}. (*) Any graph H_{∗} with k vertices and e(H_{∗}) edges contains at least

(r − 2)e(H_{∗}) − (r − 3)\binom{k + 1}{2}

K_{−}^{r}-connected pairs of vertices. □ To check that (*) is indeed an asymptotic form of Turan’s theorem, observe that if λ = λ(H_{∗}) = e(H_{∗})\binom{|H_{∗}|}{2}^{−1} is the ‘density’ of H_{∗} = H_{∗}^{k}, then the lower bound in (*) for the number of K_{−}^{r}-connected pairs in H_{∗} is, for large k,

∼ ((r − 2)λ − r + 3)\binom{k}{2}.  (17)

Note that (17) is bigger than (1/(r − 1))\binom{k}{2} for λ > 1 − 1/(r − 1). Therefore we may deduce that any (large) H_{∗} with λ(H_{∗}) > 1 − 1/(r − 1) necessarily contains a K^{r}, which is, of course, a weak form of Turán’s theorem. Unfortunately, (*) does not seem to imply Turán’s theorem for K^{r} in its precise form.

In the sequel we shall need, however, a weighted version of (*) for r = 4. To describe this version we need some technical definitions. Also, to simplify the notation we restrict ourselves to the case r = 4. (The general case does not present any further difficulty.) We start with a graph H_{∗} = H_{∗}^{k} of order k and assume γ = (γ_{e})_{e∈E(H_{∗})} is an assignment of weights γ_{e} ≥ 0 to the edges e ∈ E(H_{∗}) of H_{∗}. Suppose x = (x_{1}, …, x_{k}) is an ordering of the vertices of H_{∗}. For any two not necessarily distinct vertices x, y ∈ V (H_{∗}) that form a K_{−}^{4}-connected pair in H_{∗}, we let

w_{H_{∗},γ}(x, y) = max{γ_{1}γ_{2}: ∃z_{1}, z_{2} ∈ V (H_{∗}) with γ_{i} = γ_{z_{i}y} (i ∈ {1, 2})
and xz_{1}, xz_{2}, z_{1}z_{2}, z_{1}y, z_{2}y ∈ E(H_{∗})}.

For convenience, if x, y do not form a K_{−}^{4}-connected pair, we put w_{H_{∗},γ}(x, y) = 0. Let

w(H_{∗}, γ, x) = ∑_{1≤i≤j≤k} w_{H_{∗},γ}(x_{i}, x_{j})

and γ(H_{∗}) = ∑_{e∈E(H_{∗})} γ_{e}. Our weighted version of (*) for r = 4 is given in Lemma 15 below. We remark that to deduce the unweighted case (*) for r = 4 from this lemma, it suffices to take γ̄ = 1 and γ_{e} = 1 for all edges e ∈ E(H_{∗}).

Lemma 15. Let H_{∗} = H_{∗}^{k} be a graph of order k and edge weights γ = (γ_{e})_{e∈E(H_{∗})} with 0 ≤ γ_{e} ≤ γ̄ for all e ∈ E(H_{∗}), where γ̄ ≥ 1. Then there is an ordering x = (x_{1}, …, x_{k}) of the vertices of H_{∗} for which we have

w(H_{∗}, γ, x) ≥ 2γ(H_{∗}) − γ̄\binom{k + 1}{2}.  (18)

Proof. Our proof is by induction on k. Since the case k ≤ 3 is trivial, we assume that k ≥ 4 and that our lemma holds for graphs H_{∗} with at most 3 vertices. Note that if γ(H_{∗}) ≤ γ̄k^{2}/4, then (18) is trivially true, as in this case 2γ(H_{∗}) − γ̄\binom{k+1}{2} ≤ γ̄(k^{2}/2 − k(k + 1)/2) = −γ̄k/2 ≤ 0. Thus we may assume that γ(H_{∗}) > γ̄k^{2}/4. Since γ_{e} ≤ γ̄ for all e ∈ E(H_{∗}), we have that H_{∗} has more than k^{2}/4 edges. Therefore, there are three vertices y_{1}, y_{2}, and y_{3} ∈ V (H_{∗}) inducing a triangle in H_{∗}. For y ∈ V (H_{∗}), let us write d^{γ}(y) = d^{H_{∗},γ}(y) = ∑_{z∈Γ_{H∗} (y)} γ_{yz} for the γ-degree of y. We may assume that d^{γ}(y_{1}) ≤ d^{γ}(y_{2}) ≤ d^{γ}(y_{3}). Put x_{1} = y_{1}, and by induction let x′ = (x_{2}, …, x_{k}) be an ordering of the vertices of H′_{∗} = H_{∗} − x_{1} = H_{∗} − y_{1} such that

w(H′_{∗}, γ, x′) ≥ 2γ(H′_{∗}) − γ̄\binom{k}{2}.

For simplicity, γ above stands for the restriction (γ_{e})_{e∈E(H′_{∗})} of γ = (γ_{e})_{E(H_{∗})} to H′_{∗}. Our aim now is to estimate ∑_{1≤i≤k} w_{H_{∗},γ}(x_{1}, x_{i}) from below. For j ∈ {2, 3}, set γ_{i}(j) = γ_{y_{j}x_{i}} if y_{j}x_{i} ∈ E(H_{∗}) and set γ_{i}(j) = 0 otherwise. Now observe that, since γ̄ ≥ 1, for any reals 0 ≤ α ≤ γ̄ and 0 ≤ β ≤ γ̄ we have αβ ≥ α + β − γ̄. Therefore

\begin{matrix}∑_{1≤i≤k} w_{H_{∗},γ}(x_{1}, x_{i}) ≥ ∑_{1≤i≤k} γ_{i}(2)γ_{i}(3) ≥ ∑_{1≤i≤k} \{γ_{i}(2) + γ_{i}(3) − γ̄\} \\ = d^{γ}(y_{2}) + d^{γ}(y_{3}) − γ̄k ≥ 2d^{γ}(y_{1}) − γ̄k = 2d^{γ}(x_{1}) − γ̄k. \end{matrix}

Hence, with x = (x_{1}, x_{2}, …, x_{k}), we have

w(H_{∗}, γ, x) ≥ ∑_{1≤i≤k} w_{H_{∗},γ}(x_{1}, x_{i}) + w_{H′_{∗},γ}(H′_{∗}, γ, x′)

≥ 2d^{γ}(x_{1}) − γ̄k + 2γ(H′_{∗}) − γ̄\binom{k}{2} = 2γ(H_{∗}) − γ̄\binom{k + 1}{2},

as required. □

3.2. Pivotal pairs in subgraphs of random graphs. In this section we turn to the study of K_{−}^{4}-connected pairs in subgraphs of random graphs. Recall that given a graph H and two distinct vertices x, y ∈ V (H), we say that the unordered pair xy = {x, y} is a K_{−}^{4}-connected pair if they are the endvertices of a copy of K_{−}^{4} in H, and that a single vertex by itself forms a K_{−}^{4}-connected pair if it belongs to a triangle of H. Our main aim here is to prove Lemma 16 below, which roughly says that, if a subgraph H ⊂ G_{p} = G_{n,p} of G_{p} is such that e(H) ≥ λe(G_{p}) for some fixed λ > 0 and p = p(n) is not too small, then the number of K_{−}^{4}-connected pairs in H is, almost surely,

≳ (2λ − 1)\binom{n}{2}.

This result is similar in spirit to assertion (*) in Section 3.1, but note that (*) applied to H ⊂ G_{p} above gives nothing if p = p(n) → 0 as n → ∞. Lemma 16 below remedies this situation and recovers essentially the same lower bound for the number of K_{−}^{4}-connected pairs.

In the sequel, for any given graph H, it will be convenient to define a graph Π = Π_{H} on V (H) by letting two distinct vertices x, y ∈ V (H) = V (Π) be adjacent in Π if and only if they form a K_{−}^{4}-connected in H.

Lemma 16. Let a constant 0 < σ ≤ 1 be given. Then there is a constant C_{0} = C_{0}(σ) that depends only on σ for which the following holds. If p = p(n) = ωn^{−2/5} and C_{0} ≤ ω = ω(n) = o(n^{1/190}), then almost every G_{p} = G_{n,p} is such that, for any subgraph H ⊂ G_{p} of G_{p}, we have

e(Π_{H}) ≥ (2λ − 1 − σ)\binom{n}{2},  (19)

where λ = e(H) \{p\binom{n}{2}\}^{−1}.

Before we proceed, let us remark that we shall apply Lemma 16 above with σ much smaller than λ. In fact, we shall be interested in the case in which λ is a little greater than 2/3 and σ is very small.

The proof of Lemma 16 is based on the results of the previous three sections and on a further technical lemma, Lemma 17, which we now describe. The context in which Lemma 17 applies is as follows. Suppose 0 < μ ≤ 1/2, 0 < κ ≤ 1, 0 < δ′ ≤ 1, 0 < γ̄_{0} ≤ 1, and 0 < ρ̄ ≤ 1/4 are constants, and let n and m ≥ κn be integers. Let also 0 < p = p(n) ≤ 1 be given. Let V̄_{1}, V̄_{2}, Z̄_{1}, and Z̄_{2} be pairwise disjoint sets of cardinality (1−μ)m ≤ m_{j} = |V̄_{j}| ≤ m and (1−μ)m ≤ m′_{i} = |Z̄_{i}| ≤ m (i, j ∈ {1, 2}). Suppose F = F_{1}∪F_{2} is a graph with F_{j} a tripartite graph with tripartition V (F_{j}) = V̄_{j} ∪ Z̄_{1} ∪ Z̄_{2} (j ∈ {1, 2}) and such that E(F [Z̄_{1}, Z̄_{2}]) = E(F_{j}[Z̄_{1}, Z̄_{2}]) for both j ∈ {1, 2}. For simplicity, put γ_{Z} = d_{F,p}(Z̄_{1}, Z̄_{2}) and let γ_{ij} = d_{F,p}(Z̄_{i}, V̄_{j}) for i, j ∈ {1, 2}. Suppose further that the following conditions hold:

(i) We have γ_{Z} ≥ γ̄_{0} and γ_{ij} ≥ γ̄_{0} for all i, j ∈ {1, 2}.

(ii) At least (1 − δ′)m_{1} vertices x in V̄_{1} are such that

k_{3}^{F} (x) ≥ (1 − ρ̄ − δ′)γ_{11}γ_{21}γ_{Z}p^{3}m′_{1}m′_{2},

where k_{3}^{F} (x) is the number of triangles of F that contain x.

(iii) At least (1 − δ′)e(F [Z̄_{1}, Z̄_{2}]) edges e in F [Z̄_{1}, Z̄_{2}] are such that

k_{3}^{F} (e, V̄_{2}) ≥ (1 − δ′)γ_{12}γ_{22}p^{2}m_{2},  (20)

where k_{3}^{F} (e, V̄_{2}) denotes the number of triangles in F determined by the edge e and some vertex in V̄_{2}.

(iv) Let c = γ̄_{0}^{3}κ^{2}/8. For any x ∈ V̄_{1}, E ⊂ E(F [Γ_{F} (x)]), and W ⊂ V̄_{2} with |E| ≥ cp^{3}n^{2} and |W | ≥ cn, we have

k_{3}^{F} (E, W) ≤ (1 + \frac{δ′}{4} ) p^{2}|E||W |.

(v) For all E ⊂ E(F [Z̄_{1}, Z̄_{2}]) with |E| ≥ pn^{2}/ log n and W ⊂ V̄_{1} with |W | ≥

n/ log n, we have k_{3}^{F} (E, W) ≤ 2p^{2}|E||W |. We may now state a key technical lemma in the proof of Lemma 16.

Lemma 17. Let constants 0 < γ̄_{0} ≤ 1 and 0 < σ ≤ 1 be given. Then, with the notation above, if δ′ ≤ δ′_{0} = δ′_{0}(γ̄_{0}, σ) = σ^{2}γ̄_{0}/128 and μ ≤ μ_{0} = μ_{0}(σ) = σ/8, then the number of K_{−}^{4}-connected pairs x_{1}x_{2} with x_{j} ∈ V̄_{j} (j ∈ {1, 2}) is at least (1 − σ)γ_{12}γ_{22}m^{2}.

Proof. Let us put α = μ_{0} = σ/8 and note that then δ′_{0} = σ^{2}γ̄_{0}/128 = α^{2}γ̄_{0}^{2}/2. Let 0 < δ′ ≤ δ_{0} and 0 < μ ≤ μ_{0} be given, and suppose that F is as described before our lemma.

In the sequel, an edge e ∈ E(F [Z̄_{1}, Z̄_{2}]) will be said to be (δ′, K^{3}; F_{2})-poor if (20) fails. For x ∈ V̄_{1}, let us write k_{3}^{p}(x) for the number of (δ′, K^{3}; F_{2})-poor edges e ∈ E(F [Z̄_{1}, Z̄_{2}]) induced by the neighbourhood of x in F. Let us say that x ∈ V̄_{1} is unusable if k_{3}^{p}(x) ≥ αγ_{11}γ_{21}γ_{Z}p^{3}m′_{1}m′_{2}. The proof is now split into a few claims. Assertion 1. At most αm_{1} vertices in V̄_{1} are unusable. Suppose the contrary. Let us consider the number N of pairs (x, e) with x a vertex in V̄_{1} and e a (δ′, K^{3}; F_{2})-poor edge in E(F [Z̄_{1}, Z̄_{2}]) such that there is a triangle of F containing both x and e. Since we are assuming that more than αm_{1} vertices x ∈ V̄_{1} are unusable, we have

N > α^{2}γ_{11}γ_{21}γ_{Z}p^{3}m′_{1}m′_{2}m_{1} ≥ α^{2}γ̄_{0}^{2}γ_{Z}p^{3}m′_{1}m′_{2}m_{1}.  (21)

We now use condition (v) above to deduce that

N ≤ 2p^{2}m_{1}δ′e(F [Z̄_{1}, Z̄_{2}]) = 2δ′γ_{Z}p^{3}m′_{1}m′_{2}m_{1}  (22)

Comparing (21) and (22), we obtain that α^{2}γ̄_{0}^{2} < 2δ′, contradicting the fact that δ′ ≤ δ′_{0} = α^{2}γ̄_{0}/2. Thus Assertion 1 holds.

We now observe that condition (ii) above immediately implies the following. Assertion 2. For at least (1 − 2α)m_{1} vertices x in V̄_{1}, we have k_{3}^{F} (x) − k_{3}^{p}(x) ≥ c_{1}p^{3}n^{2}, where c_{1} = (1 − ρ̄ − 2α)(1 − μ)^{2}κ^{2}γ̄_{0}^{3} ≥ c.

Now let x ∈ V̄_{1} be given. Let E_{x} ⊂ E(F [Z̄_{1}, Z̄_{2}]) be the set of edges e induced by the neighbourhood of x in F that are not (δ′, K^{3}; F_{2})-poor. Thus |E_{x}| = k_{3}^{F} (x) − k_{3}^{p}(x). Let

W_{x} = {y ∈ V̄_{2}: E(F [Γ_{F} (x)]) ∩ E(F [Γ_{F} (y)]) ≠ ∅}
= {y ∈ V̄_{2}: xy is a K_{−}^{4}-connected pair}.

Assertion 3. For at least (1 − 2α)m_{1} vertices x ∈ V̄_{1}, we have |W_{x}| ≥ (1 − σ/2)γ_{12}γ_{22}m_{2}. Let x ∈ V̄_{1} be such that |E_{x}| = k_{3}^{F} (x) − k_{3}^{p}(x) ≥ c_{1}p^{3}n^{2}, and suppose that |W_{x}| < (1 − σ/2)γ_{12}γ_{22}m_{2}. We now use (iv) above to deduce that

\begin{aligned}(1 − δ′)γ_{12}γ_{22}p^{2}m_{2}|E_{x}| & ≤ k_{3}^{F} (E_{x}, W_{x}) ≤ (1 + \frac{δ′}{4} ) p^{2}|E_{x}||W_{x}| \\ & ≤ (1 + \frac{δ′}{4} ) (1 − \frac{σ}{2} ) γ_{12}γ_{22}p^{2}m_{2}|E_{x}|, \end{aligned}

which is a contradiction since 1 − δ′ > (1 + δ′/4)(1 − σ/2). Thus any x ∈ V̄_{1} with |E_{x}| = k_{3}^{F} (x) − k_{3}^{p}(x) ≥ c_{1}p^{3}n^{2} is such that |W_{x}| ≥ (1 − σ/2)γ_{12}γ_{22}m_{2}, and hence Assertion 3 follows from Assertion 2.

From Assertion 3, we deduce that at least

\begin{aligned}(1 − 2α) & (1 − \frac{σ}{2} ) γ_{12}γ_{22}m_{1}m_{2} \\ & ≥ (1 − 2α)(1 − μ)^{2} (1 − \frac{σ}{2} ) γ_{12}γ_{22}m^{2} ≥ (1 − σ)γ_{12}γ_{22}m^{2} \end{aligned}

pairs x_{1}x_{2} (x_{j} ∈ V̄_{j}, j ∈ {1, 2}) are K_{−}^{4}-connected with respect to F, thereby proving Lemma 17. □

We are now ready to prove Lemma 16. Our proof will make use of several of our previous lemmas.

Proof of Lemma 16. Let 0 < σ ≤ 1 be given. We now define the many constants with which we shall apply Lemmas 4, 5, 7, 9, 10, 14, 15, and 17.

Let γ_{0} = σ/100, γ̄_{0} = γ_{0}/2, α = γ_{0}/24e and k_{0} = ⌈100/σ⌉. Let δ = (δ′)^{2}/2, where δ′ = σ^{3}/2 × 10^{6} ≤ δ′_{0} = δ′_{0}(γ̄_{0}, σ/7) = σ^{2}γ̄_{0}/6272. Note that δ′_{0}(γ̄_{0}, σ/7) is as given in Lemma 17. We now let

ε = min \{10^{−16}σ^{6}γ_{0}, \frac{1}{2}ε_{0}(α, γ̄_{0}, δ)\} ,

where ε_{0} = ε_{0}(α, γ̄_{0}, δ) is as defined in Lemma 7. Put ε̄ = 2ε, ρ = 2ε/γ_{0} and ρ̄ = 5ε/γ_{0}. For later reference, note that

ρ̄ = \frac{5ε}{γ_{0}} ≤ 5 × 10^{−16}σ^{6} ≤ \frac{δ}{27},  (23)

and if k ≥ k_{0}, then, with plenty to spare, we have

\frac{2σ}{7(k − 1)} + \frac{6}{k − 1} ≤ \frac{σ}{7} ,  (24)

and

\frac{3ε}{γ_{0}} + \frac{1}{k} ≤ \frac{2}{7}σ.  (25)

Set μ = 6ε ≤ μ_{0}(σ/7), where μ_{0}(σ/7) = σ/56 is as given in Lemma 17. Now let K_{0} = K_{0}(ε, k_{0}) and η = η(ε, k_{0}) be as given by Lemma 4. We may assume that η ≤ min{σ/7, ε/2K_{0}}. Put κ = 1/2K_{0}, and let c = γ̄_{0}^{3}κ^{2}/8. Finally, let C_{0} = C_{0}(c, c, δ′/4), where C_{0}(c, c, δ′/4) is as given by Lemma 10. We claim that this choice of C_{0} = C_{0}(σ) will do in Lemma 16, and proceed to prove this assertion.

Let p = p(n) = ωn^{−2/5}, where C_{0} ≤ ω = ω(n) = o(n^{1/190}). Let us consider the following conditions for G_{p} = G_{n,p}.

(a) G_{p} is η-upper-uniform and has size e(G_{p}) = (1 + o(1))p\binom{n}{2}.

(b) Suppose m ≥ κn. Then, for any T ≥ (3/4)γ̄_{0}pm^{2} and any m = (m_{1}, m_{2}, m_{3}) with m/2 ≤ m_{i} ≤ m (i ∈ {1, 2, 3}), our G_{p} contains no copy of any graph F ∈ F_{p}^{δ}(ε̄, γ̄_{0}, ρ̄; m, T) as a subgraph.

(c) Inequality (10) in Lemma 10 holds for all E and W as in the statement of that lemma with c_{1} = c_{2} = c and θ = δ′/4.

(d) Relation (15) in Lemma 14 holds for all E ⊂ E(G_{p}) and W ⊂ V (G_{p})\V (E)

with |E| ≥ pn^{2}/ log n and |W | ≥ n/ log n. Claim. Conditions (a)–(d) hold for almost every G_{p}. Proof of the Claim. Condition (a) clearly holds almost surely. We use Lemma 7 to prove that (b) holds almost surely as well. Let m, m, and T be as in (b). Note that the number of choices for m and m is trivially at most n^{4}. The number of copies of a fixed graph F ∈ F_{p}^{δ}(ε̄, γ̄_{0}, ρ̄; m, T) that the complete graph K^{n} on n vertices contains is clearly at most n^{n}. Thus, since ρ̄ ≤ δ/27 (see (23)) and ε̄ = 2ε ≤ ε_{0}(α, γ̄_{0}, δ), Lemma 7 applies to give that the expected number of copies of elements from F_{p}^{δ}(ε̄, γ̄_{0}, ρ̄; m, T) that G_{p} contains is, for sufficiently large n, at most

n^{4+n}|F_{p}^{δ}(ε̄, γ̄_{0}, ρ̄; m, T)|p^{T} ≤ n^{4+n}α^{T} \binom{3m^{2}}{T}p^{T} ≤ n^{4+n} (\frac{3eαpm^{2}}{T} )^{T} ,

which, since T ≥ (3/4)γ̄_{0}pm^{2}, is at most

n^{4+n} (\frac{8eα}{γ_{0}})^{T} ≤ n^{4+n}3^{−T} ≤ 2^{−T} .

Summing over all T ≥ (3/4)γ̄_{0}pm^{2}, we obtain that (b) holds almost always. Condition (c) holds almost surely for G_{p} by Lemma 10 and the choice of C_{0}. To check that (d) holds for a.e. G_{p}, by Lemma 14 it suffices to see that pn^{1/2}/ log n → ∞ and that (pn^{2}/ log n)/np^{−1} log n → ∞ as n → ∞. This completes the proof of our claim.

In the remainder of the proof, we show that (19) holds for any subgraph H ⊂ G_{p} whenever G_{p} satisfies conditions (a)–(d) above. This clearly proves our lemma. Thus let us assume that H ⊂ G_{p} is given and that G_{p} satisfies (a)–(d). We may clearly assume that H is a spanning subgraph of G_{p}.

Let us apply Lemma 4 to the η-upper-uniform graph H, with parameters ε and k_{0}. Let V (H) = V_{0} ∪ ⋯ ∪ V_{k} be the (ε, H, p)-regular (ε, k)-equitable partition we obtain in this way. Let H′ be the subgraph of H on ⋃_{1≤i≤k} V_{i} with e ∈ E(H) an edge of H′ if and only if e joins two vertices that belong to distinct classes of our regular partition, say, V_{i} and V_{j} (1 ≤ i < j ≤ k), with (V_{i}, V_{j}) an (ε, H, p)- regular pair and d_{H,p}(V_{i}, V_{j}) ≥ γ_{0}. In the sequel, we let m stand for the common cardinality of the sets V_{i} (1 ≤ i ≤ k). Recall that λ = e(H) \{p\binom{n}{2}\}^{−1}. We now check the following simple fact.

Assertion 1. We have e(H′) ≥ (λ − σ/7)p\binom{n}{2} provided n is sufficiently large. From the η-upper-uniformity of H it follows that if W ⊂ V = V (H), |W | ≥ 2ηn then e(H[W]) ≤ (1 + η)p\binom{|W |}{2}. Hence e(H[V_{0}]) ≤ (3/5)ε^{2}pn^{2}. Also, e_{H}(V_{0}, V \ V_{0}) is at most (1 + η)p|V_{0}||V \ V_{0}| ≤ (6/5)εpn^{2}. Thus the number of edges of H incident to V_{0} is at most 4εp\binom{n}{2} for large enough n. Now note that ∑ e_{H}(V_{i}, V_{j}) with the sum over all 1 ≤ i < j ≤ k such that (V_{i}, V_{j}) is not (ε, H, p)-regular is at most ε\binom{k}{2}(1 + η)pm^{2} ≤ 2εp\binom{n}{2}. Also, ∑ e_{H}(V_{i}, V_{j}) with the sum extended over all 1 ≤ i < j ≤ k such that d_{H,p}(V_{i}, V_{j}) ≤ γ_{0} is at most (1 + η)γ_{0}\binom{k}{2}pm^{2} ≤ 2γ_{0}p\binom{n}{2}. Finally, we have that ∑_{1≤i≤k} e(H[V_{i}]) ≤ k(1 + η)p\binom{m}{2} ≤ (2p/k)\binom{n}{2}. Therefore |E(H) \ E(H′)| ≤ (6ε + 2/k + 2/γ_{0})p\binom{n}{2} ≤ (σ/7)p\binom{n}{2} if n is sufficiently large, as required.

We now define a graph H_{∗} on [k] = {1, …, k} by letting ij (1 ≤ i < j ≤ k) be an edge of H_{∗} if and only if (V_{i}, V_{j}) is an (ε, H, p)-regular pair and d_{H,p}(V_{i}, V_{j}) ≥ γ_{0}. We write γ_{ij} for d_{H,p}(V_{i}, V_{j}) for all ij ∈ E(H_{∗}), and put γ = (γ_{e})_{e∈E(H_{∗})}. Now put γ̄ = 1 + σ/7, and notice that then the definition of η and (a) above gives that γ_{e} ≤ 1 + η ≤ γ̄ for all e ∈ E(H_{∗}).

Lemma 15 now tells us that, suitably adjusting the notation, the ordering x = (1, …, k) of the vertices of H_{∗} is such that

w(H_{∗}, γ, x) = ∑_{1≤i≤j≤k} w_{H_{∗},γ}(i, j) ≥ 2γ(H_{∗}) − γ̄\binom{k + 1}{2}.  (26)

In our next assertion we bound γ(H_{∗}).

Assertion 2. We have γ(H_{∗}) = ∑_{e∈E(H_{∗})} γ_{e} ≥ (λ − σ/7)\binom{k}{2}.

Indeed, we have e(H′) = ∑_{e∈E(H_{∗})} γ_{e}pm^{2} = γ(H_{∗})pm^{2}, and hence, by Assertion 1,

γ(H_{∗}) ≥ \frac{1}{m^{2}} (λ − \frac{σ}{7} ) \binom{n}{2} ≥ (λ − \frac{σ}{7} ) \binom{n}{2} /\frac{k^{2}}{n^{2}} ≥ (λ − \frac{σ}{7} ) \binom{k}{2}.

Our next step relates the number of K_{−}^{4}-connected pairs meeting two fixed classes V_{i} and V_{j} (1 ≤ i < j ≤ k) with the summand w_{H_{∗},γ}(i, j) appearing in (26). Assertion 3. Suppose ι_{1}, ι_{2} ∈ [k] are two distinct vertices of H_{∗}. Then the number of K_{−}^{4}-connected pairs x_{1}x_{2} with x_{j} ∈ V_{ι_{j}} (j ∈ {1, 2}) is at least

(1 − σ/7 − 2ε/γ_{0})w_{H_{∗},γ}(ι_{1}, ι_{2})m^{2}.

The above assertion is an easy consequence of Lemma 17, although we shall have to work a little to check that that lemma does apply here.

Let us start by observing that, trivially, if ι_{1} and ι_{2} are not K_{−}^{4}-connected in H_{∗}, then by definition w_{H_{∗},γ}(ι_{1}, ι_{2}) = 0, and hence there is nothing to prove. Thus let us assume that this is not the case, and let ι_{3}, ι_{4} ∈ [k] be two vertices of H_{∗} such that ι_{1}ι_{3}, ι_{1}ι_{4}, ι_{3}ι_{4}, ι_{2}ι_{3}, ι_{2}ι_{4} ∈ E(H_{∗}). Choosing ι_{3} and ι_{4} suitably, we may further assume that w_{H_{∗},γ}(ι_{1}, ι_{2}) = γ_{ι_{2}ι_{3}}γ_{ι_{2}ι_{4}}. We may now restrict our attention to the 4-partite subgraph of H induced by the V_{ι_{a}} (1 ≤ a ≤ 4).

Let J = H[V_{ι_{1}}, V_{ι_{2}}, V_{ι_{3}}, V_{ι_{4}}] and write L for the graph on [4] = {1, 2, 3, 4} isomorphic to K_{−}^{4}, with 1 and 2 as the endvertices. We first apply Lemma 5 to J to obtain Ū_{ι_{a}} ⊂ V_{ι_{a}} (1 ≤ a ≤ 4) such that the following holds. Putting m_{a} = |Ū_{ι_{a}}|, we have (1 − μ)m ≤ m_{a} ≤ m for all 1 ≤ a ≤ 4 and, furthermore, if ab ∈ E(L) and x ∈ Ū_{ι_{a}}, then

d_{ab}(x) = |Γ_{J}(x) ∩ Ū_{ι_{b}}| = (1 + O_{1}(ρ))d_{J,p}(V_{ι_{a}}, V_{ι_{b}})pm.  (27)

Let F = J[Ū_{ι_{1}}, Ū_{ι_{2}}, Ū_{ι_{3}}, Ū_{ι_{4}}]. Since d_{J,p}(V_{ι_{a}}, V_{ι_{b}}) = d_{F,p}(Ū_{ι_{a}}, Ū_{ι_{b}}) + O_{1}(ε) and d_{F,p}(Ū_{ι_{a}}, Ū_{ι_{b}}) ≥ γ_{0} − ε ≥ γ̄_{0} = γ_{0}/2, we have

d_{J,p}(V_{ι_{a}}, V_{ι_{b}}) = (1 + O_{1}(2ε/γ_{0}))d_{F,p}(Ū_{ι_{a}}, Ū_{ι_{b}}).

Moreover, as (1−μ)m ≤ m_{b} ≤ m, we have m = (1+O_{1}(2μ))m_{b}. Thus, relation (27) gives that, for any x ∈ Ū_{ι_{a}},

d_{ab}(x) = (1 + O_{1}(ρ̄))d_{F,p}(Ū_{ι_{a}}, Ū_{ι_{b}})pm_{b},

where, as defined above, ρ̄ = 5ε/γ_{0}. Note also that γ̄_{0} ≤ d_{F,p}(Ū_{ι_{a}}, Ū_{ι_{b}}) ≤ γ̄ = 1 + σ/7 (cf. condition (a) above).

Our immediate aim now is to apply Lemma 17. To make our current notation the same as the one used in that lemma, let us put V̄_{j} = Ū_{ι_{j}} and Z̄_{j} = Ū_{2+j} for j ∈ {1, 2} and F_{j} = J[V̄_{j}, Z̄_{1}, Z̄_{2}] (j ∈ {1, 2}). Clearly, F = J[V̄_{1}, V̄_{2}, Z̄_{1}, Z̄_{2}] = F_{1} ∪ F_{2} and F [Z̄_{1}, Z̄_{2}] = F_{1}[Z̄_{1}, Z̄_{2}] = F_{2}[Z̄_{1}, Z̄_{2}]. Also, let m_{j} = |V̄_{j}| and m′_{i} = |Z̄_{i}| (i, j ∈ {1, 2}).

Let m_{j} = (m_{j}, m′_{1}, m′_{2}) and T_{j} = e(F_{j}) ≥ (3/4)γ̄_{0}pm^{2} (j ∈ {1, 2}). Observe that by (b) above we may conclude that

F_{j} = H[V̄_{j}, Z̄_{1}, Z̄_{2}] ∈ F_{p}(ε̄, γ̄_{0}, ρ̄; m_{j}, T_{j}) \ F_{p}^{δ}(ε̄, γ̄_{0}, ρ̄; m_{j}, T_{j})

for both j ∈ {1, 2}. We shall now invoke Lemma 17, but to see that that lemma does apply we verify the following claim. Claim. Conditions (i)–(v) given before the statement of Lemma 17 hold. Proof of the Claim. Condition (i) has already been seen to hold. To see that (ii) holds, we simply apply Lemma 9 to the (δ, K^{3})-balanced graph F_{1}. Now, condition (iii) clearly holds as F_{2} is (δ, K^{3})-balanced. Finally, condition (iv) is equivalent to (c), while condition (v) follows from (d). This finishes the proof of our claim.

In view of the above claim and the definitions of δ′_{0} = δ′_{0}(γ̄_{0}, σ/7) and μ_{0} = μ_{0}(σ/7), we see that we may indeed apply Lemma 17 to deduce that the number of K_{−}^{4}-connected pairs x_{1}x_{2} with x_{j} ∈ V_{ι_{j}} (j ∈ {1, 2}) is at least

(1 − \frac{σ}{7} ) d_{F,p}(Z̄_{1}, V̄_{2})d_{F,p}(Z̄_{2}, V̄_{2})m^{2}.  (28)

We now use that, for i ∈ {1, 2}, we have

d_{F,p}(Z̄_{i}, V̄_{2}) ≥ d_{H,p}(V_{ι_{2}}, V_{ι_{i+2}}) − ε ≥ (1 − \frac{ε}{γ_{0}} ) d_{H,p}(V_{ι_{2}}, V_{ι_{i+2}}),

since d_{H,p}(V_{ι_{2}}, V_{ι_{i+2}}) ≥ γ_{0}. Thus the quantity in (28) is at least

\begin{matrix}(1 − \frac{σ}{7} ) (1 − \frac{ε}{γ_{0}} )^{2} d_{H,p}(V_{ι_{2}}, V_{ι_{3}})d_{H,p}(V_{ι_{2}}, V_{ι_{4}})m^{2} \\ ≥ (1 − \frac{σ}{7} − \frac{2ε}{γ_{0}}) γ_{ι_{2}ι_{3}}γ_{ι_{2}ι_{4}}m^{2}, \end{matrix}

which concludes the proof Assertion 3, since ι_{3} and ι_{4} were chosen so as to have w_{H_{∗},γ}(ι_{1}, ι_{2}) = γ_{ι_{2}ι_{3}}γ_{ι_{2}ι_{4}}.

The proof of our lemma is completed in the next assertion. Recall that Π_{H} stands for the graph on V (H) with two vertices of H adjacent in Π_{H} if and only if they are K_{−}^{4}-connected in H. Assertion 4. We have e(Π_{H}) ≥ (2λ − 1 − σ)\binom{n}{2}. By Assertion 3 we have that

e(Π_{H}) ≥ ∑_{1≤i<j≤k} e(Π_{H}[V_{i}, V_{j}]) ≥ ∑_{1≤i<j≤k} (1 − \frac{σ}{7} − \frac{2ε}{γ_{0}}) w_{H_{∗},γ}(i, j)m^{2}. (29)

Now, clearly, we have

\begin{aligned}∑_{1≤i<j≤k} w_{H_{∗},γ}(i, j) & = w(H_{∗}, γ, x) − ∑_{1≤i≤k} w_{H_{∗},γ}(i, i) \\ & ≥ w(H_{∗}, γ, x) − γ̄^{2}k ≥ w(H_{∗}, γ, x) − 2k, \end{aligned}

since γ̄^{2} = (1 + σ/7)^{2} ≤ 2. Thus, recalling (26) and using that m ≥ (1 − ε)n/k, we have from (29) that e(Π_{H}) is at least

(1 − \frac{σ}{7} − \frac{2ε}{γ_{0}}) (1 − ε)^{2} \frac{n^{2}}{k^{2}} (w(H_{∗}, γ, x) − 2k)

≥ (1 − \frac{σ}{7} − \frac{3ε}{γ_{0}}) \frac{n^{2}}{k^{2}} (2γ(H_{∗}) − γ̄\binom{k + 1}{2} − 2k) ,

which, by Assertion 2, is at least

(1 − \frac{σ}{7} − \frac{3ε}{γ_{0}}) (1 − \frac{1}{k} ) (2 (λ − \frac{σ}{7} )−(1 + \frac{σ}{7} ) \binom{k + 1}{2}\binom{k}{2}^{−1} −2k\binom{k}{2}^{−1})\binom{n}{2},

which is, as one may check using (24) and (25), at least

(1 − \frac{σ}{7} − \frac{3ε}{γ_{0}} − \frac{1}{k} ) (2λ − 1 − \frac{4σ}{7} ) \binom{n}{2} ≥ (2λ − 1 − σ)\binom{n}{2},

proving Assertion 4.

The proof of Lemma 16 is complete. □

§4. Proof of the Main Result

We first prove Theorem 2 under the extra hypothesis that p = p(n) should not be too large. More precisely, we prove the following result. Recall that we write G →_{γ} H if any subgraph J of G with e(J) ≥ γe(G) contains a copy of H.

Lemma 18. Let a constant η > 0 be given. Then there is a constant C = C(η) that depends only on η for which the following holds. If 0 ≤ p = p(n) = ωn^{−2/5} ≤ 1 and C ≤ ω = ω(n) = o(n^{1/190}), then almost every G_{p} = G_{n,p} is such that G_{p} →_{2/3+η} K^{4}.

Proof. Let ε = σ = η/10 and k = ⌈1+24(log 2)η^{−2}⌉. Let C = kC_{0}(σ), where C_{0}(σ) is as given in Lemma 16. We shall show that this choice of C = C(η) will do in our result. Thus let p = p(n) be as in the statement of Theorem 2, and consider the space G(n, p) of the random graphs G_{n,p} = G_{p}. In this proof, we shall write G_{p} as a union of sparser, independent random graphs.

Let p_{1} be such that 1−p = (1−p_{1})^{k}, and note that then p/k ≤ p_{1} = (1+o(1))p/k. Put Ω = ∏_{1≤j≤k} G(n, p_{1}). We shall write G = (G_{p_{1}}^{(1)}, …, G_{p_{1}}^{(k)}) for a general random

element of Ω. Thus the G_{p_{1}}^{(j)} (1 ≤ j ≤ k) are independent random graphs, each taken from G(n, p_{1}). For any given G = (G_{p_{1}}^{(1)}, …, G_{p_{1}}^{(k)}) ∈ Ω, let us put G_{p} = G_{p}(G) = G_{p_{1}}^{(1)}∪⋯∪G_{p_{1}}^{(k)}, and note that then the map G = (G_{p_{1}}^{(j)})_{1≤j≤k} ∈ Ω ↦ G_{p} = G_{p}(G) ∈ G(n, p) is measure-preserving. We may thus study G(n, p) investigating the random elements G ∈ Ω. Let us define Ω′ ⊂ Ω by letting G = (G_{p_{1}}^{(j)})_{1≤j≤k} ∈ Ω belong to Ω′ if and only if (i) e(G_{p}) = (1 + O_{1}(ε))p\binom{n}{2}, (ii) e(G_{p_{1}}^{(j)}) = (1 + O_{1}(ε))(p/k)\binom{n}{2} for all 1 ≤ j ≤ k and, finally, (iii) for all 1 ≤ j ≤ k, the graph G_{p_{1}}^{(j)} has the property that if E ⊂ E(G_{p_{1}}^{(j)}) and λ = |E| \{p_{1}\binom{n}{2}\}^{−1}, then

e(Π_{E}) ≥ (2λ − 1 − σ)\binom{n}{2}.  (30)

For simplicity, Π_{E} above stands for Π_{H}, where H = H(E) is the graph on V (G_{p}) with edge set E.

Elementary facts concerning random graphs and Lemma 16 gives that ℙ(Ω′) = 1 − o(1). In the sequel, we shall often condition on Ω′ and we shall write ℙ′(A) for the conditional probability ℙ(A | Ω′) for any event A ⊂ Ω.

Let B ⊂ Ω be the set of G = (G_{p_{1}}^{(1)}, …, G_{p_{1}}^{(k)}) that admit a set F ⊂ E(G_{p}) with |F | ≥ (2/3 + η)e(G_{p}) but G_{p}[F] ⊅ K^{4}. We need to show that ℙ(B) = o(1), or, equivalently, that ℙ′(B) = o(1). Let us put B′ = B ∩ Ω′. For each G ∈ B, let us fix once and for all a set F = F (G) ⊂ E(G_{p}) as required in the definition of B. Let us also put F^{(j)} = F^{(j)}(G) = F ∩ E(G_{p_{1}}^{(j)}) (1 ≤ j ≤ k) and set f = f(G) = |F | and f^{(j)} = f^{(j)}(G) = |F^{(j)}| (1 ≤ j ≤ k).

Now let γ^{(j)} = γ^{(j)}(G) = f^{(j)}/p_{1}\binom{n}{2}, and note that then we have f ≤ f^{(1)} + ⋯ + f^{(k)}, and hence that

\frac{2}{3} + η ≤ γ^{(1)} \frac{p_{1}\binom{n}{2}}{e(G_{p})} + ⋯ + γ^{(k)} \frac{p_{1}\binom{n}{2}}{e(G_{p})} ≤ \frac{1}{k} (\frac{1 + ε}{1 − ε}) (γ^{(1)} + ⋯ + γ^{(k)}) ,

from which we conclude that

γ^{∗} = γ^{∗}(G) = max_{1≤j≤k} γ^{(j)} ≥ Ave_{1≤j≤k} γ^{(j)} ≥ \frac{1 − ε}{1 + ε} (\frac{2}{3} + η) ≥ \frac{2}{3}(1 + η),  (31)

where the last inequality follows from the choice of ε. Let us also note that

γ^{∗} ≤ 1 + ε,  (32)

since we are assuming that (ii) above holds. For each 1 ≤ j ≤ k, let

B′_{j} = {G ∈ B′: γ^{(j)}(G) = γ^{∗}(G)}.

Clearly B′ = ⋃_{1≤j≤k} B′_{j}, and hence it suffices to show that ℙ′(B′_{j}) = o(1) for all j. Thus we now fix j ∈ [k] and proceed to show that B′_{j} almost surely does not hold. We have

ℙ′(B′_{j}) = ∑_{G_{0}} ℙ′(B′_{j} ∩ {G ∈ Ω : G_{p_{1}}^{(j)} = G_{0}})

= ∑_{G_{0}} ℙ′(B′_{j} | G_{p_{1}}^{(j)} = G_{0})ℙ′(G_{p_{1}}^{(j)} = G_{0})

≤ max_{G_{0}} ℙ′(B′_{j} | G_{p_{1}}^{(j)} = G_{0}),  (33)

where G_{0} ranges over all graphs on V (G_{p}) with e(G_{0}) = (1 + O_{1}(ε))(p/k)\binom{n}{2} and such that (30) holds for all E ⊂ E(G_{0}) with λ = |E|/p_{1}\binom{n}{2}. We now fix one such G_{0} and proceed to show an upper bound for (33). For each F_{0} ⊂ E(G_{0}), let

P′(j, G_{0}, F_{0}) = ℙ′(G ∈ B′_{j}, F^{(j)} = F_{0} | G_{p_{1}}^{(j)} = G_{0}).  (34)

Then

ℙ′(B′_{j} | G_{p_{1}}^{(j)} = G_{0}) = ∑_{F_{0}⊂E(G_{0})} P′(j, G_{0}, F_{0}) ≤ 2^{(1+ε) \frac{p}{k} \binom{n}{2}} max_{F_{0}⊂E(G_{0})} P′(j, G_{0}, F_{0}).

(35)

We now fix F_{0} and estimate the last term in (35) from above. We may of course assume that P′(j, G_{0}, F_{0}) > 0 for the fixed triple (j, G_{0}, F_{0}) under consideration, as otherwise there is nothing to prove. Thus we may in particular assume that |F_{0}|/p_{1}\binom{n}{2} ≥ (2/3)(1 + η). Let us write B′(j, G_{0}, F_{0}) for the set of G ∈ B′_{j} such that G_{p_{1}}^{(j)} = G_{0} and F^{(j)} = F_{0}. To show that P′(j, G_{0}, F_{0}) is small, we argue that if G = (G_{p_{1}}^{(i)})_{1≤i≤k} ∈ B′(j, G_{0}, F_{0}), then the edges of the graphs G_{p_{1}}^{(i)} (i ≠ j, 1 ≤ i ≤ k) are distributed in a rather unlikely way.

Let p_{2} be such that 1 − p_{2} = (1 − p_{1})^{k−1}, and note that then p_{2}/(k − 1) ≤ p_{1} = (1 + o(1))p_{2}/(k − 1). For any given G = (G_{p_{1}}^{(i)})_{1≤i≤k} ∈ Ω, we write G_{p_{2}}^{(¬j)} for ⋃_{i} G_{p_{1}}^{(i)}, where the union is taken over all i ≠ j (1 ≤ i ≤ k). Thus G_{p_{2}}^{(¬j)} is a random element from G(n, p_{2}), and G_{p} = G_{p_{1}}^{(j)} ∪ G_{p_{2}}^{(¬j)}. Note also that if G ∈ Ω′, then e(G_{p_{2}}^{(¬j)}) ≤ (1 + 2ε)p_{2}\binom{n}{2}.

For any G = (G_{p_{1}}^{(i)})_{1≤i≤k} ∈ Ω, let F′ = F′(G) = E(G_{p_{2}}^{(¬j)}) ∩ E(Π_{F_{0}}). Also, let f′ = f′(G) = |F′| for any G ∈ Ω. Clearly, f′ = f′(G) (G ∈ Ω) is binomially distributed with parameters e(Π_{F_{0}}) and p_{2}. In fact, it is clear that f′ = f′(G) has this distribution even if we condition on G being such that G_{p_{1}}^{(j)} = G_{0}. We now verify the following claim, from which we shall deduce an exponential upper estimate for P′(j, G_{0}, F_{0}). In the sequel, we write 𝔼_{G_{0}} for the expectation in the space Ω ∩ {G: G_{p_{1}}^{(j)} = G_{0}}. Claim. If G ∈ B′(j, G_{0}, F_{0}) then f′ ≤ (1 − η)𝔼_{G_{0}}(f′).

Proof of the Claim. Let us fix G = (G_{p_{1}}^{(j)})_{1≤j≤k} ∈ B′(j, G_{0}, F_{0}). Let F^{(¬j)} = F^{(¬j)}(G) = F ∩ E(G_{p_{2}}^{(¬j)}), and put f^{(¬j)} = f^{(¬j)}(G) = |F^{(¬j)}|. Clearly F^{(¬j)} ∪ F′ ⊂ E(G_{p_{2}}^{(¬j)}) and, since F spans no K^{4}, we have F^{(¬j)} ∩ F′ = ∅. Thus we have f^{(¬j)} + f′ ≤ e(G_{p_{2}}^{(¬j)}) ≤ (1 + 2ε)p_{2}\binom{n}{2}, and hence

f′ ≤ (1 + 2ε − γ^{(¬j)})p_{2}\binom{n}{2},  (36)

where γ^{(¬j)} = γ^{(¬j)}(G) = f^{(¬j)}/p_{2}\binom{n}{2}. We now show that γ^{(¬j)} is suitably large. We have f = |F | ≤ f^{(j)} + f^{(¬j)}, and hence

\frac{2}{3} + η ≤ γ^{(j)} \frac{p_{1}\binom{n}{2}}{e(G_{p})} + γ^{(¬j)} \frac{p_{2}\binom{n}{2}}{e(G_{p})} ≤ \frac{1}{k} (\frac{1 + ε}{1 − ε}) (γ^{(j)} + (k − 1)γ^{(¬j)}) .

Therefore

\frac{2}{3}(1 + η) ≤ \frac{1}{k} γ^{(j)} + \frac{k − 1}{k}γ^{(¬j)} ≤ \frac{1}{k} γ^{∗} + \frac{k − 1}{k}γ^{(¬j)} ≤ \frac{1}{k} (1 + ε) + γ^{(¬j)},

where the last inequality follows from (32). Thus we conclude that γ^{(¬j)} ≥ 2/3. We now note that μ = 𝔼_{G_{0}}(f′) = p_{2}e(Π_{F_{0}}) ≥ (2γ^{∗} − 1 − σ)p_{2}\binom{n}{2}. Note that, in particular, by (31) and the choice of σ, we have (1/3)p_{2}\binom{n}{2} ≤ μ ≤ p_{2}\binom{n}{2}. Let b denote the right-hand side of (36). Then

\begin{matrix}μ − b ≥ (2γ^{∗} − 1 − σ − 1 − 2ε + γ^{(¬j)}) p_{2}\binom{n}{2} \\ ≥ (\frac{4η}{3} − 2ε − σ) p_{2}\binom{n}{2} ≥ ηp_{2}\binom{n}{2} ≥ ημ, \end{matrix}

and therefore f′ ≤ b ≤ (1 − η)μ, as claimed.

We now use our claim to bound P′(j, G_{0}, F_{0}), which, we recall, is defined in (34) above. Recall also that f′ ∼ Bi(e(Π_{F_{0}}), p_{2}). We have

P′(j, G_{0}, F_{0}) ≤ ℙ \{f′ ≤ (1 − η)𝔼_{G_{0}}(f′) | G_{p_{1}}^{(j)} = G_{0}\} ≤ exp \{−\frac{1}{2}η^{2}μ\} ,

where, as remarked before, μ = 𝔼_{G_{0}}(f′) = e(Π_{F_{0}})p_{2} ≥ (1/3)p_{2}\binom{n}{2}. Thus, from (35) we deduce that

ℙ′(B′_{j} | G_{p_{1}}^{(j)} = G_{0}) ≤ 2^{(1+ε) \frac{p}{k} \binom{n}{2}} exp \{−\frac{1}{6}η^{2} (1 − \frac{1}{k} ) p\binom{n}{2}\}

= exp \{((1 + ε)(log 2) − \frac{k − 1}{6}η^{2}) \frac{p}{k} \binom{n}{2}\}

≤ exp \{−\frac{1}{12} (1 − \frac{1}{k} ) η^{2}p\binom{n}{2}\}

≤ exp \{−\frac{1}{30}η^{2}pn^{2}\} .

We now recall (33) to deduce that ℙ′(B′_{j}) ≤ exp{η^{2}pn^{2}/30} = o(1), completing the proof of Lemma 18. □

We next show that, loosely speaking, the quantity ex(G_{n,p}, H)\{p\binom{n}{2}\}^{−1} is nonincreasing in probability for any fixed graph H. In particular, this shows that Lemma 18 implies Theorem 2.

Lemma 19. Suppose 0 ≤ p = p(n) ≤ 1, 0 < γ = γ(n) ≤ 1, and 0 < ε = ε(n) ≤ 1 are such that ε^{2}γpn^{2} → ∞ as n → ∞. Suppose also that G_{n,p} →_{γ} H holds almost surely for some graph H. Then, if 0 ≤ p′ = p′(n) ≤ 1 is such that p′ ≥ p for all large enough n, we almost surely have G_{n,p′} →_{γ(1+ε)} H.

Proof. Write γ′ = γ′(n) = γ(1 + ε). Let p′ = p′(n) be as in the statement of our lemma. Suppose for a contradiction that G_{n,p′} →_{γ′} H fails with probability at least θ > 0 for arbitrarily large values of n, where θ is some positive absolute constant. Put λ = λ(n) = p(n)/p′(n) ≤ 1. Note that we may generate G_{n,p} by first generating G_{n,p′} and then randomly removing its edges, each with probability 1 − λ, and with all these deletions independent. Looking at this method for generating G_{n,p}, we shall deduce below that the probability that (*) G_{n,p} →_{γ} H fails is at least θ/3 for arbitrarily large n, which is a contradiction.

Let δ = ε/4. For arbitrarily large n, with probability at least 2θ/3 we have that (†) G_{n,p′} →_{γ′} H fails and e(G_{n,p′}) = (1 + O_{1}(δ))p′\binom{n}{2}. Suppose that, when generating G_{n,p} by the above method, we first generated a G_{n,p′} satisfying (†) above. Let J = J(G_{n,p′}) ⊂ G_{n,p′} be an H-free subgraph of G_{n,p′} with e(J) ≥ γ′e(G_{n,p′}). Clearly, the H-free subgraph J_{λ} = J ∩ G_{n,p} of J is a subgraph of our G_{n,p}. We have e(J_{λ}) = (1 + O_{1}(δ))λe(J) and e(G_{n,p}) = (1 + O_{1}(δ))λe(G_{n,p′}) with probability 1 − o(1), and hence we have e(J_{λ}) ≥ γe(G_{n,p}) with probability 1 − o(1). Therefore, given that G_{n,p′} satisfies (†) above, the probability that we generate a G_{n,p} for which (*) fails is 1 − o(1). Since the probability that we generate G_{n,p} satisfying (†) is at least 2θ/3 for arbitrarily large n, we conclude that our G_{n,p} will fail to satisfy (*) with probability at least θ/3 for arbitrarily large n, which is the contradiction we were after. □

Proof of Theorem 2. Theorem 2 follows at once from Lemmas 18 and 19. □

A simple variant of the method used in the proof of Lemma 19 gives the following ‘equivalence result’ between the binomial and the uniform models of random graphs with respect to the property G →_{γ} H.

Lemma 20. Let H be a graph. Consider the following two assertions. S_{bin}(γ, p): G_{n,p} →_{γ} H holds almost surely, S_{unif}(γ, M): G_{n,M} →_{γ} H holds almost surely,

where 0 < γ = γ(n) ≤ 1, 0 < p = p(n) ≤ 1, and 0 < M = M(n) ≤ \binom{n}{2} are arbitrary functions. Suppose ω = ω(n) → ∞ as n → ∞. Then the following holds.

(i) Suppose pn^{2} → ∞, ω = o(np^{1/2}), and h = h(n) = ωnp^{1/2}. Let γ′ = γ′(n) = γ + 2h/M′ and M′ = M′(n) = ⌈p\binom{n}{2} + h⌉. Then S_{bin}(γ, p) implies S_{unif}(γ′, M′).

(ii) Suppose M = M(n) → ∞, ω = o(M^{1/2}), and h = h(n) = ωM^{1/2}. Let γ′ = γ′(n) = γ + 2h/M, and p′ = p′(n) = (M + h)\binom{n}{2}^{−1}. Then S_{unif}(γ, M) implies S_{bin}(γ′, p′).

Proof. Let us prove (i). Assume S_{bin}(γ, p) holds. We may generate G_{n,M′} by first generating G_{n,p} conditioned on the event E = {e(G_{n,p}) ≤ M′}, and then randomly adding M′ − e(G_{n,p}) edges to it so as to have a graph with M′ edges. For clarity, let us write G_{n,p}^{E} for our binomial random graph G_{n,p} conditioned on E. Note that ℙ(E) = 1 − o(1), and hence the effect of conditioning on E is, so to speak, negligible. We now claim that G_{n,M′} →_{γ′} H holds with probability 1 − o(1).

Suppose our claim fails, and hence, for arbitrarily large n, there exists with probability at least θ > 0 an H-free subgraph J ⊂ G_{n,M′} of G_{n,M′} with e(J) ≥ γ′e(G_{n,M′}), where θ is some positive absolute constant. Observe that if J ⊂ G_{n,M′} is an H-free subgraph of G_{n,M′}, then, obviously, J′ = J ∩ G_{n,p}^{E} ⊂ G_{n,p}^{E} is an Hfree subgraph of G_{n,p}^{E}. Now note that almost surely we have M′ − e(G_{n,p}^{E}) ≤ 2h, and hence almost surely ex(G_{n,p}^{E}, H) ≥ ex(G_{n,M′}, H) − 2h. Since we are assuming that ex(G_{n,M′}, H) ≥ γ′e(G_{n,M′}) with probability θ > 0 for arbitrarily large n, we have

ex(G_{n,p}^{E}, H) ≥ γ′e(G_{n,M′}) − 2h ≥ γ′M′ − 2h ≥ γe(G_{n,p}^{E})

with probability θ/2 for arbitrarily large n. Since G_{n,p}^{E} is the binomial random graph G_{n,p} conditioned on the almost sure event E, we deduce that ex(G_{n,p}, H) ≥ γe(G_{n,p}) with probability at least θ/3 for arbitrarily large n, contradicting S_{bin}(γ, p). Thus S_{unif}(γ′, M′) follows. The proof of (ii) is similar. □

Proof of Corollary 3. Corollary 3 follows easily from Theorem 2 and Lemma 20. □

§5. Deterministic Consequences

In this section we give a few results concerning the existence of very sparse graphs G = G_{η} that satisfy G →_{2/3+η} K^{4} for any fixed η > 0.

If H is a graph of order |H| ≥ 3 and size e(H) ≥ 1, recall that its 2-density is d_{2}(H) = (e(H) − 1)/(|H| − 2). For an integer k ≥ 3, let H_{k} be the family of all graphs H with 3 ≤ |H| ≤ k, e(H) ≥ 1, and d_{2}(H) > d_{2}(K^{4}). Also, let Forb(H_{k}) be the collection of all graphs G that are H-free for all H ∈ H_{k}. The following result may be proved by the so called ‘deletion method’. (For details, see [8, 9].)

Theorem 21. Let 0 < η ≤ 1/3 and k ≥ 3 be fixed. Then there exists a graph G = G_{η,k} ∈ Forb(H_{k}) such that G →_{2/3+η} K^{4}. □

We now single out a corollary to Theorem 21. In Corollary 22 below, the property that G belongs to Forb(H_{k}) in Theorem 21 is replaced by a collection of simpler and more concrete conditions. For instance, one of these conditions is that G should not contain a copy of K^{5}. To state another condition that appears in Corollary 22, we need to introduce a definition.

Let G be a graph. Suppose K_{1}, …, K_{h} (h ≥ 2) are distinct copies of K^{4} in G, and e_{1} ∈ E(K_{1}), …, e_{h−1} ∈ E(K_{h−1}) are h − 1 edges of G such that E(K_{i}) ∩ ⋃_{1≤j<i} E(K_{j}) = {e_{i−1}} and V (K_{i})∩⋃_{1≤j<i} V (K_{j}) = V (e_{i}) for all 2 ≤ i ≤ h. Then we say that (K_{1}, …, K_{h}) is an (h, K^{4})-path in G. Now assume that (K_{1}, …, K_{h}) is an (h, K^{4})-path in G and that the edge e ∈ E(G) joins a vertex in V (K_{1}) \ ⋃_{1<j≤h} V (K_{j}) to a vertex in V (K_{h}) \ ⋃_{1≤i<h} V (K_{i}). Then, (K_{1}, …, K_{h}; e) is said to be an (h, K^{4})-quasi-cycle in G.

It is immediate to check that if (K_{1}, …, K_{h}) is an (h, K^{4})-path, then H = ⋃_{1≤j≤h} K_{j} has 2-density d_{2}(H) = d_{2}(K^{4}). Also, if (K_{1}, …, K_{h}; e) is an (h, K^{4})- quasi-cycle, then H′ = H + e has 2-density d_{2}(H′) > d_{2}(K^{4}).

Corollary 22. For any 0 < η ≤ 1/3 and k ≥ 1, there is a graph G = G_{η,k} such that (i) G contains no K^{5}, (ii) any two copies of K^{4} in G share at most two vertices, (iii) G contains no (h, K^{4})-quasi-cycles for any 2 ≤ h ≤ k, and (iv) G →_{2/3+η} K^{4}. □

We remark that Erdős and Nešetřil have raised the question as to whether the graphs G_{η,k} as in Corollary 22 exist.

§6. A Conjecture

In this short paragraph we state a conjecture from which, if true, one may deduce Conjecture 1. Let H = H^{h} be a graph of order |H| = h ≥ 3 and suppose H has vertices v_{1}, …, v_{h}. Let 0 < p = p(m) ≤ 1 be given. Let also V = (V_{i})_{i=1}^{h} be a family of h pairwise disjoint sets, each of cardinality m. Suppose reals 0 < ε ≤ 1 and 0 < γ ≤ 1 and an integer T are given. We say that an h-partite graph F with h-partition V (F) = V_{1} ∪ ⋯ ∪ V_{h} and size e(F) = |F | = T is an (ε, γ, H; V, T)- graph if the pair (V_{i}, V_{j}) is (ε, F, p)-regular and has p-density γ ≤ d_{F,p}(V_{i}, V_{j}) ≤ 2 whenever v_{i}v_{j} ∈ E(H).

Conjecture 23. Let constants 0 < α ≤ 1 and 0 < γ ≤ 1 be given. Then there are constants ε = ε(α, γ) > 0 and C = C(α, γ) such that, if p = p(m) ≥ Cm^{−1/d_{23}(H)}, the number of H-free (ε, γ, H; V, T)-graphs is at most

α^{T} \binom{\binom{h}{2}m^{2}}{T}

for all T and all sufficiently large m.

If H above is a forest, Conjecture 23 holds trivially, since, in this case, all (ε, γ, H; V, T)-graphs contain a copy of H. A lemma in Kohayakawa, Łuczak, and Rödl [12] may be used to show that Conjecture 23 holds for the case in which H = K^{3}. In fact, this lemma from [12] is similar in spirit to Lemma 8 above, although much simpler.

Acknowledgements

We are indebted to B. Kreuter for a careful reading of the manuscript.

References

1. Babai, L., Simonovits, M., Spencer, J.H., Extremal subgraphs of random graphs, J. Graph Theory 14 (1990), 599–622.

2. Bollobás, B., Extremal Graph Theory, Academic Press, London, 1978.

3. , Random Graphs, Academic Press, London, 1985.

4. Chung, F.R.K., Subgraphs of a hypercube containing no small even cycles, J. Graph Theory 16 (1992), 273–286.

5. Frankl, P., Rödl, V., Large triangle-free subgraphs in graphs without K_{4}, Graphs and Combinatorics 2 (1986), 135–244.

6. Füredi, Z., Random Ramsey graphs for the four-cycle, Discrete Math. 126 (1994), 407–410.

7. Haxell, P.E., Kohayakawa, Y., Łuczak, T., The induced size-Ramsey number of cycles, Combinatorics, Probability, and Computing (to appear).

8. , Turán’s extremal problem in random graphs: forbidding odd cycles, Combinatorica (to appear).

9. , Turán’s extremal problem in random graphs: forbidding even cycles, J. Combinatorial Theory, Series B 64 (1995), 273–287.

10. Janson, S., Poisson approximation for large deviations, Random Structures and Algorithms 1 (1990), 221–230.

11. Kohayakawa, Y., Kreuter, B., Steger, A., An extremal problem for random graphs and the number of graphs with large even-girth (1995), submitted.

12. Kohayakawa, Y., Łuczak, T., Rödl, V., Arithmetic progressions of length three in subsets of a random set, Acta Arithmetica (to appear).

13. Rödl, V., Ruciński, A., Lower bounds on probability thresholds for Ramsey properties, Combinatorics—Paul Erdős is Eighty (Volume 1) (Miklós, D., Sós, V.T., Szőnyi, T., eds.), Bolyai Soc. Math. Studies, Budapest, 1993, pp. 317–346.

14. , Threshold functions for Ramsey properties, J. Amer. Math. Soc. (to appear).

15. Szemerédi, E., Regular partitions of graphs, Problèmes Combinatoires et Théorie des Graphes, Proc. Colloque Inter. CNRS (Bermond, J.-C., Fournier, J.-C., Las Vergnas, M., Sotteau, D., eds.), CNRS, Paris, 1978, pp. 399–401.

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

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

Department of Discrete Mathematics, Adam Mickiewicz University, ul. Matejki 48/49, 60–769 Poznań, Poland

   E-mail address: <tomasz@math.amu.edu.pl>, <tomasz@mathcs.emory.edu>

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

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