Combinatorics, Probability and Computing (19XX) 00, 000–000. Printed in the United Kingdom \begin{matrix}c \\ ◯ \end{matrix} 19XX Cambridge University Press

The Turán Theorem for Random Graphs

YOSHIHARU KOHAYAKAWA,^{1}† VOJTĚCH RÖDL,^{2}‡ and MATHIAS SCHACHT^{2}

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

                         (e-mail: yoshi@ime.usp.br)

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

                 (e-mail: {rodl, mschach}@mathcs.emory.edu)

The aim of this paper is to prove a Turán type theorem for random graphs. For 0 < γ and graphs G and H, write G →_{γ} H if any γ-proportion of the edges of G spans at least one copy of H in G. We show that for every graph H and every fixed real δ > 0 almost every graph G in the binomial random graph model G(n, q), with q = q(n) ≫ ((log n)^{4}/n)^{1/d(H)}, satisfies G →_{(χ(H)−2)/(χ(H)−1)+δ} H, where as usual χ(H) denotes the chromatic number of H and d(H) is the “degeneracy number” of H.

Since K_{l}, the complete graph on l vertices, is l-chromatic and (l − 1)-degenerate we infer that for every l ≥ 2 and every fixed real δ > 0 almost every graph G in the binomial random graph model G(n, q), with q = q(n) ≫ ((log n)^{4}/n)^{1/(l−1)}, satisfies G →_{(l−2)/(l−1)+δ} K_{l}.

CONTENTS

1 Introduction 2 2 Preliminary results 4

2.1 Preliminary definitions 4 2.2 The regularity lemma for sparse graphs 4 2.3 The counting lemma for complete subgraphs of random graphs 5

3 The main result 6 3.1 Properties of almost all graphs 6 3.2 A deterministic subgraph lemma 7 3.3 Proof of the main result 10

† Research supported in part by MCT/CNPq through ProNEx Programme (Proc. CNPq 664107/1997–

4), by CNPq (Proc. 300334/93–1 and 468516/2000–0). ‡ Research supported in part by an NSF Grant 0071261. The collaboration of the authors is supported

by a CNPq/NSF cooperative grant (910064/99–7, 0072064).

4 The counting lemma 12 4.1 The pick-up lemma 13 4.2 The k-tuple lemma for subgraphs of random graphs 18 4.3 Outline of the proof of the counting lemma for l = 4 19 4.4 Proof of the counting lemma 21

5 The d-degenerate case 28 References 31

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

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(F)|: H ⊄ F ⊂ G}. For instance, if G = K_{n}, the complete graph on n vertices, then ex(K_{n}, H) = ex(n, H) is the usual Turán number of H.

Our aim here is to study ex(G, H) when G is a random graph. Let 0 < q = q(n) ≤ 1 be given. The binomial random graph G in G(n, q) has as its vertex set a fixed set V (G) of cardinality n and two vertices are adjacent in G with probability q. All such adjacencies are independent. (For concepts and results concerning random graphs not given in detail below, see, e.g., Bollobás [2].) Here we wish to investigate the random variables ex(G(n, q), H), where H = K_{l} (l ≥ 2) or H is a d-degenerate graph, a graph that may be reduced to the empty graph by the successive removal of vertices of degree less or equal d.

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(H′) − 1}{|H′| − 2} : H′ ⊂ H, |H′| ≥ 3\} .

A general conjecture concerning ex(G(n, q), H), first stated in [10], is as follows (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 in G(n, q) satisfies P if P holds with probability tending to 1 as n → ∞).

Conjecture 1.1. Let H be a non-empty graph of order at least 3, and let 0 < q = q(n) ≤ 1 be such that qn^{1/d_{2}(H)} → ∞ as n → ∞. Then almost every G in G(n, q) satisfies

ex(G, H) = (1 − \frac{1}{χ(H) − 1} + o(1)) |E(G)|.

In other words, for G in G(n, q) the Conjecture 1.1 claims that G →_{γ} H holds almost surely for any fixed γ > 1 − 1/(χ(H) − 1). There are a few results in support of Conjecture 1.1.

Any result concerning the tree-universality of expanding graphs, or any simple application of Szemerédi’s regularity lemma for sparse graphs (see Theorem 2.2 below), gives Conjecture 1.1 for H a forest. The cases in which H = K_{3} and H = C_{4} are essentially proved in Frankl and Rödl [3] and Füredi [4], respectively, in connection with problems concerning the existence of some graphs with certain extremal properties. The case for H = K_{4} was proved by Kohayakawa, Łuczak, and Rödl [10] and the case in which H is a general cycle was settled by Haxell, Kohayakawa, and Łuczak [5, 6] (see also Kohayakawa, Kreuter, and Steger [9]).

Our main result relates to Conjecture 1.1 in the following way: we deal with the case in which H = K_{l} and q = q(n) ≫ ((log n)^{4}/n)^{1/(l−1)}. More precisely we prove the following.

Theorem 1.2. Let l ≥ 2, q = q(n) ≫ ((log n)^{4}/n)^{1/(l−1)}, and let G(n, q) be the binomial random graph model with edge probability q. Then for every 1/(l − 1) > δ > 0 a graph G in G(n, q) satisfies the following property with probability 1 − o(1): If F is an arbitrary, not necessarily induced subgraph of G with

|E(F)| ≥ (1 − \frac{1}{l − 1} + δ) q\binom{n}{2},

then F contains K_{l}, the complete graph on l vertices, as a subgraph. Moreover, there exists a constant c = c(δ, l) such that F contains at least cq^{\binom{l}{2}}n^{l} copies of K_{l}.

In this paper we give a proof of Theorem 1.2.† In Section 5 we outline the proof of an extension of this result, Theorem 1.2′ (the detailed proof is given in [14]).

Recall that a graph H with |V (H)| = h is d-degenerate if there exists an ordering of the vertices v_{1}, …, v_{h} such that each v_{i} (1 ≤ i ≤ h) has at most d neighbours in

† Very recently, Szabó and Vu [16] proved independently the same result under a slightly weaker assumption; in fact, they proved Theorem 1.2 for q(n) ≫ n^{−1/(l−3/2)}. Their proof is elegant. To obtain the smaller lower bound for q, they make use of the fact that Conjecture 1.1 holds for H = K_{4} [10] as the base of an induction; without using this result, their proof gives essentially the same condition on q as ours. Their approach extends to several infinite families of graphs H (see [16, Section 4]); the present proof extends to all graphs, and works for q(n) ≫ ((log n)^{4}/n)^{1/d}, where d = d(H) is the “degeneracy number” of the graph H; see Theorem 1.2′.

{v_{1}, …, v_{i−1}} (for more details concerning d-degenerate graphs see [13, 15]). Since K_{l} is clearly (l − 1)-degenerate and l-chromatic, the following result extends Theorem 1.2.

Theorem 1.2′. Let d be a positive integer, H a d-degenerate graph on h vertices, q = q(n) ≫ ((log n)^{4}/n)^{1/d}, and G(n, q) the binomial random graph model with edge probability q. Then for every 1/(χ(H) − 1) > δ > 0 a graph G in G(n, q) satisfies the following property with probability 1 − o(1): If F is an arbitrary, not necessarily induced subgraph of G with

|E(F)| ≥ (1 − \frac{1}{χ(H) − 1} + δ) q\binom{n}{2},

then F contains H as a subgraph. Moreover, there exists a constant c = c(δ, H) such that F contains at least cq^{|E(H)|}n^{h} copies of H.

This paper is organized as follows. In Section 2 we describe a sparse version of Szemerédi’s regularity lemma (Theorem 2.2) and we state the counting lemma (Lemma 2.3), which are crucial in our proof of Theorem 1.2. We prove Theorem 1.2 in Section 3. Section 4 is entirely devoted to the proof of Lemma 2.3. The proof of Lemma 2.3 relies on the ‘Pick-Up Lemma’ (Lemma 4.3) and on the ‘k-tuple lemma’ (Lemma 4.7). We give these preliminary results in Section 4.1–4.2. In Section 4.3 we outline the proof of Lemma 2.3 in the case l = 4. Finally, the proof is given in Section 4.4. We discuss the case when H is a d-degenerate graph and sketch the proof of Theorem 1.2′ in Section 5.

For a general remark about the notation we use throughout this paper see the remark in Section 2.3.

Acknowledgement. The authors thank the referee for his or her detailed work.

2. Preliminary results

2.1. Preliminary definitions Let a graph G = G^{n} of order |V (G)| = n be fixed. For U, W ⊂ V = V (G), we write

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

for the set of edges of G that have one end-vertex in U and the other in W. Notice that each edge in U ∩ W occurs only once in E(U, W). We set e(U, W) = e_{G}(U, W) = |E(U, W)|.

If G is a graph and V_{1}, …, V_{t} ⊂ V (G) are disjoint sets of vertices, we write G[V_{1}, …, V_{t}] for the t-partite graph naturally induced by V_{1}, …, V_{t}.

2.2. The regularity lemma for sparse graphs Our aim in this section is to state a variant of the regularity lemma of Szemerédi [17].

Let a graph H = H^{n} = (V, E) of order |V | = n be fixed. Suppose ξ > 0, C > 1, and 0 < q ≤ 1.

Definition 2.1 ((ξ, C)-bounded). For ξ > 0 and C > 1 we say that H = (V, E) is a (ξ, C)-bounded graph with respect to density q, if for all U, W ⊂ V, not necessarily disjoint, with |U|, |W | ≥ ξ|V |, we have

e_{H}(U, W) ≤ Cq (|U||W | − \binom{|U ∩ W |}{2}) .

For any two disjoint non-empty sets U, W ⊂ V, let

d_{H,q}(U, W) = \frac{e_{H}(U, W)}{q|U||W |}.  (2)

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

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

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

Below, we shall sometimes use the expression ε-regular with respect to density q to mean that (U, W) is an (ε, q)-regular pair.

We say that a partition P = (V_{i})_{0}^{t} of V = V (H) is (ε, t)-equitable if |V_{0}| ≤ εn, and |V_{1}| = ⋯ = |V_{t}|. Also, we say that V_{0} is the exceptional class of P. When the value of ε is not relevant, we refer to an (ε, t)-equitable partition as a t-equitable partition. Similarly, P is an equitable partition of V if it is a t-equitable partition for some t.

We say that an (ε, t)-equitable partition P = (V_{i})_{0}^{t} of V is (ε, H, q)-regular, or simply (ε, q)-regular, if at most ε\binom{t}{2} pairs (V_{i}, V_{j}) with 1 ≤ i < j ≤ t are not (ε, q)-regular. We may now state a version of Szemerédi’s regularity lemma for (ξ, C)-bounded graphs.

Theorem 2.2. For any given ε > 0, C > 1, and t_{0} ≥ 1, there exist constants ξ = ξ(ε, C, t_{0}) and T_{0} = T_{0}(ε, C, t_{0}) ≥ t_{0} such that any sufficiently large graph H that is (ξ, C)-bounded with respect to density 0 < q ≤ 1 admits an (ε, H, q)-regular (ε, t)-equitable partition of its vertex set with t_{0} ≤ t ≤ T_{0}.

A simple modification of Szemerédi’s proof of his lemma gives Theorem 2.2. For applications of this variant of the regularity lemma and its proof, see [8, 12].

2.3. The counting lemma for complete subgraphs of random graphs Let t ≥ l ≥ 2 be fixed integers and n a sufficiently large integer. Let α and ε be constants greater than 0. Let G ∈ G(n, q) be the binomial random graph with edge probability q = q(n), and suppose J is an l-partite subgraph of G with vertex classes V_{1}, …, V_{l}. For all 1 ≤ i < j ≤ l we denote by J_{ij} the bipartite graph induced by V_{i} and V_{j}. Consider the following assertions for J. (I) |V_{i}| = m = n/t (II) q^{l−1}n ≫ (log n)^{4} (III) J_{ij} has T = pm^{2} edges where 1 > αq = p ≫ 1/n, and (IV) J_{ij} is (ε, q)-regular.

Remark. Strictly speaking, in (I) we should have, say, ⌊m/t⌋, because m is an integer. However, throughout this paper we will omit the floor and ceiling signs ⌊ ⌋ and ⌈ ⌉, since they have no significant effect on the arguments. Moreover, let us make a few more comments about the notation that we shall use. For positive functions f(n) and g(n), we write f(n) ≫ g(n) to mean that lim_{n→∞} g(n)/f(n) = 0. Unless otherwise stated, we understand by o(1) a function approaching zero as the number of vertices of a given random graph goes to infinity.

Finally, we observe that our logarithms are natural logarithms.

We are interested in the number of copies of complete graphs on l vertices in such a subgraph J satisfying conditions (I)–(IV).

Lemma 2.3 (Counting lemma). For every α, σ > 0 and integer l ≥ 2 there exists ε > 0 such that for every fixed integer t ≥ l a random graph G in G(n, q) satisfies the following property with probability 1 − o(1): Every subgraph J ⊆ G satisfying conditions (I)–(IV) contains at least

(1 − σ)p^{\binom{l}{2}}m^{l}

copies of the complete graph K_{l}.

We will prove Lemma 2.3 later in Section 4.

3. The main result

In this section we will prove the main result of this paper, Theorem 1.2. This section is organized as follows. First, we state two properties that hold for almost every G ∈ G(n, q). Then, in Section 3.2, we prove a deterministic statement about the regularity of certain subgraphs of an (ε, q)-regular α-dense t-partite graph. Finally, we prove Theorem 1.2.

3.1. Properties of almost all graphs We start with a well known fact of random graph theory which follows easily from the properties of the binomial distribution.

Fact 3.1. If G is a random graph in G(n, q), then

|E(G)| = (1 + o(1)) q\binom{n}{2}

holds with probability 1 − o(1).

The next property refers to Definition 2.1 and will enable us to apply Theorem 2.2.

Lemma 3.2. For every C > 1, ξ > 0 and q = q(n) ≫ 1/n a random graph G in G(n, q) is (ξ, C)-bounded with probability 1 − o(1).

We will apply the following one-sided estimate of a binomially distributed random variable.

Lemma 3.3. Let X be a binomial distributed random variable in Bi(N, q) with expectation 𝔼X = Nq and let C > 1 be a constant. Then

ℙ(X ≥ C𝔼X) ≤ exp(−τC𝔼X),

where τ = log C − 1 + 1/C > 0 for C > 1 (recall that all logarithms are to base e, see the remark in Section 2.3).

Proof. The proof is given in [7] (see Corollary 2.4).

Proof of Lemma 3.2. Let G ∈ G(n, q) and let U, W ⊆ V (G) be two not necessarily disjoint sets such that |U|, |W | ≥ ξn. Clearly, e(U, W) is a binomial random variable with

𝔼[e(U, W)] = q (|U||W | − \binom{|U ∩ W |}{2}) .

Observe that 𝔼[e(U, W)] ≫ n since q ≫ 1/n. Set τ = log C − 1 + 1/C. Then Lemma 3.3 implies

ℙ (e(U, W) > C𝔼[e(U, W)]) ≤ exp (−τC𝔼[e(U, W)]) .

We now sum over all choices for U and W to deduce that

ℙ(G is not (ξ, C)-bounded) ≤

∑_{|U|≥ξn} ∑_{|W |≥ξn} \binom{n}{|U|}\binom{n}{|W |} exp (−τC𝔼[e(U, W)])
≤ 4^{n} exp (−τC𝔼[e(U, W)]) = o(1),

since τC > 0 and 𝔼[e(U, W)] ≫ n.

3.2. A deterministic subgraph lemma The next lemma states that every (ε, q)-regular, bipartite graph with at least αqm^{2} edges contains an (3ε, q)-regular subgraph with exactly αqm^{2} edges.

Lemma 3.4. For every ε > 0, α > 0, and C > 1 there exists m_{0} such that if H = (U, W; F) is a bipartite graph satisfying (i ) |U| = m_{1}, |W | = m_{2} > m_{0}, (ii ) Cqm_{1}m_{2} ≥ e_{H}(U, W) ≥ αqm_{1}m_{2} for some function q = q(m_{0}) ≫ 1/m_{0}, and (iii ) H is (ε, q)-regular, then there exists a subgraph H′ = (U, W; F′) ⊆ H such that (ii′) e_{H′}(U, W) = αqm_{1}m_{2} and (iii′) H′ is (3ε, q)-regular.

Proof. We select a set D of

|D| = e_{H}(U, W) − αqm_{1}m_{2}

different edges in E_{H}(U, W) uniformly at random and fix H′ = (U, W; F \ D). We naturally define the density in D with respect to q for sets U′ ⊆ U and W′ ⊆ W by

d_{D,q}(U′, W′) = \frac{|E_{H}(U′, W′) ∩ D|}{q|U′||W′|}.  (4)

In order to check the (3ε, H′, q)-regularity of (U, W), it is enough to verify the inequality corresponding to (3) for sets U′ ⊆ U, W′ ⊆ W such that |U′| = 3εm_{1} and |W′| = 3εm_{2}. Let (U′, W′) be such a pair. We distinguish three cases depending on |D| and e_{H}(U′, W′).

Case 1 (|D| ≤ ε^{3}qm_{1}m_{2}). The graph H is (ε, H, q)-regular and thus

d_{H,q}(U′, W′) ≥ d_{H,q}(U, W) − ε.

Since d_{H′,q}(U′, W′) ≥ d_{H,q}(U′, W′) − d_{D,q}(U′, W′), we have

d_{H′,q}(U′, W′) ≥ d_{H,q}(U′, W′) − \frac{|D|}{9ε^{2}qm_{1}m_{2}} ≥ d_{H,q}(U, W) − \frac{10}{9}ε,

which implies that H′ is (3ε, q)-regular.

Case 2 (e_{H}(U′, W′) ≤ ε^{3}qm_{1}m_{2}). Observe that e_{H}(U′, W′) ≤ ε^{3}qm_{1}m_{2} implies

d_{H,q}(U′, W′) ≤ \frac{ε}{9}.  (5)

H is (ε, H, q)-regular and thus

d_{H,q}(U, W) ≤ ε + d_{H,q}(U′, W′) ≤ \frac{10}{9}ε.  (6)

On the other hand, d_{H′,q}(X, Y) ≤ d_{H,q}(X, Y) for arbitrary X ⊆ U and Y ⊆ W, which combined with (5) and (6) yields

|d_{H′,q}(U, W) − d_{H′,q}(U′, W′)| ≤ \frac{10}{9}ε + \frac{ε}{9} ≤ 3ε.

Up to now, we have not used the fact that D is chosen at random. To deal with the case that we are left with (that is, the case in which |D| > ε^{3}qm_{1}m_{2} and e_{H}(U′, W′) > ε^{3}qm_{1}m_{2}), we will make use of this randomness. Before we start, we state the following two-sided estimate for the hypergeometric distribution.

Lemma 3.5. Let sets B ⊆ U be fixed. Let |U| = u and |B| = b. Suppose we select a d-set D uniformly at random from U. Then, for 3/2 ≥ λ > 0, we have

ℙ (||D ∩ B| − \frac{bd}{u}| ≥ λ\frac{bd}{u}) ≤ 2 exp (−\frac{λ^{2}}{3} \frac{bd}{u}) .

Proof. For the proof we refer to [7] (Theorem 2.10).

We continue with the proof of Lemma 3.4.

Case 3 (|D| > ε^{3}qm_{1}m_{2} and e_{H}(U′, W′) > ε^{3}qm_{1}m_{2}). Recall that U′ ⊆ U and V′ ⊆ V are such that |U′| = 3εm_{1} and |V′| = 3εm_{2}. First, we verify that

|d_{D,q}(U, W)\frac{d_{H,q}(U′, W′)}{d_{H,q}(U, W)} − d_{D,q}(U′, W′)| ≤ ε  (7)

implies that

|d_{H′,q}(U, W) − d_{H′,q}(U′, W′)| ≤ 3ε.  (8)

Indeed, straightforward calculation using the (ε, q)-regularity of H and (7) give

|d_{H′,q}(U, W) − d_{H′,q}(U′, W′)|

= |(d_{H,q}(U, W) − d_{D,q}(U, W)) − (d_{H,q}(U′, W′) − d_{D,q}(U′, W′))| ≤ ε + |d_{D,q}(U, W) − d_{D,q}(U′, W′)|

≤ ε + |d_{D,q}(U, W) − d_{D,q}(U, W)\frac{d_{H,q}(U′, W′)}{d_{H,q}(U, W)}|

+ |d_{D,q}(U, W)\frac{d_{H,q}(U′, W′)}{d_{H,q}(U, W)} − d_{D,q}(U′, W′)|

≤ ε + \frac{d_{D,q}(U, W)}{d_{H,q}(U, W)} |d_{H,q}(U, W) − d_{H,q}(U′, W′)| + ε

≤ ε + \frac{d_{D,q}(U, W)}{d_{H,q}(U, W)}ε + ε

≤ 3ε.

Next, we will prove that (7) is unlikely to fail, because of the random choice of D. We set

λ = min \{\frac{9ε^{3}}{C} , \frac{3}{2}\} .  (9)

Then the two-sided estimate in Lemma 3.5 gives that

||D ∩ E_{H}(U′, W′)| − \frac{e_{H}(U′, W′)|D|}{e_{H}(U, W)}| < λ\frac{e_{H}(U′, W′)|D|}{e_{H}(U, W)}

fails with probability

≤ 2 exp (−\frac{λ^{2}}{3} \frac{e_{H}(U′, W′)|D|}{e_{H}(U, W)}) .  (10)

Since

|d_{D,q}(U′, W′) − d_{D,q}(U, W)\frac{d_{H,q}(U′, W′)}{d_{H,q}(U, W)}|

= \frac{1}{9ε^{2}qm_{1}m_{2}} ||D ∩ E_{H}(U′, W′)| − \frac{e_{H}(U′, W′)|D|}{e_{H}(U, W)}| ,

and because of (ii) and (9), we have

λ\frac{e_{H}(U′, W′)}{9qε^{2}m_{1}m_{2}} \frac{|D|}{e_{H}(U, W)} ≤ λ\frac{e_{H}(U′, W′)}{9qε^{2}m_{1}m_{2}} ≤ λ\frac{e_{H}(U, W)}{9qε^{2}m_{1}m_{2}} ≤ ε,

we infer that (7) and consequently (8) fails with small probability given in (10).

We now sum over all possible choices for U′ and W′ and use the conditions of this case (i.e. |D| > ε^{3}qm_{1}m_{2}, e_{H}(U′, W′) > ε^{3}qm_{1}m_{2}) and (ii). We have that

ℙ (H′ is not (3ε, q)-regular) ≤ 2^{m_{1}+m_{2}} · 2 exp (−\frac{λ^{2}ε^{6}}{3C} qm_{1}m_{2}) < 1

for m_{1}, m_{2} sufficiently large, since q = q(m_{0}) ≫ 1/m_{0}. This implies that, for m_{0} large enough, there is a set D such that H′ is (3ε, q)-regular, as required.

3.3. Proof of the main result The proof of Theorem 1.2 is based on Lemma 2.3, which we prove later in Section 4. The main idea is to “find” a regular subgraph J satisfying (I)–(IV) of the Counting Lemma, in the arbitrary subgraph F with

|E(F)| ≥ (1 − \frac{1}{l − 1} + δ) q\binom{n}{2}.

Proof of Theorem 1.2. Let l ≥ 2 and 1/(l − 1) > δ > 0 be fixed and suppose q = q(n) ≫ ((log n)^{4}/n)^{1/(l−1)}. First we define some constants that will be used in the proof.

We start by setting

α = \frac{δ}{8},  (11)
σ = 10^{−6}.  (12)

(As a matter of fact, our proof is not sensitive to the value of the constant σ; in fact, as long as 0 < σ < 1, every choice works.) We want to use the Counting Lemma, Lemma 2.3, in order to determine the value of ε. Set α^{CL} = α and σ^{CL} = σ, then Lemma 2.3 yields ε^{CL}. We set

ε = min \{\frac{ε^{CL}}{3} , \frac{δ}{80}\}  (13)

and

C = \frac{4 + δ}{4} .  (14)

We then apply the sparse regularity lemma (Theorem 2.2) with ε^{SRL} = ε, C^{SRL} = C and t_{0}^{SRL} = max\{\sqrt{8l^{2}/δ}, 40/δ\}. Theorem 2.2 then gives ξ^{SRL} and we define

ξ = ξ^{SRL}.

Moreover, Theorem 2.2 yields

T_{0}^{SRL} ≥ t = t^{SRL} ≥ t_{0}^{SRL} = max \{\sqrt{\frac{8l^{2}}{δ}} , \frac{40}{δ}\} .  (15)

For the rest of the proof all the constants defined above (α, σ, ε, C, ξ, and t) are fixed.

Fact 3.1, Lemma 3.2, and Lemma 2.3 imply that a graph G in G(n, q) satisfies the following properties (P1)–(P3) with probability 1 − o(1):

(P1) |E(G)| ≥ (1 + o(1)) q\binom{n}{2}, (P2) G is (ξ, C)-bounded, and (P3) G satisfies the property considered in Lemma 2.3.

We will show that if a graph G satisfies (P1)–(P3), then any F ⊆ G with |E(F)| ≥ (1 − 1/(l − 1) + δ)q\binom{n}{2} contains at least cq^{\binom{l}{2}}n^{l} (for some constant c = c(δ, l)) copies of K_{l}, and Theorem 1.2 will follow.

To achieve this, we first regularise F by applying Theorem 2.2 with ε^{SRL} = ε, C^{SRL} = C and t_{0}^{SRL} = max\{\sqrt{8l^{2}/δ}, 40/δ\}. Consequently F admits an (ε, q)-regular (ε, t)-equitable partition (V_{i})_{0}^{t}. We set m = n/t = |V_{i}| for i ≠ 0.

Let F_{cluster} be the cluster graph of F with respect to (V_{i})_{0}^{t} defined as follows

V (F_{cluster}) = {1, …, t},
E (F_{cluster}) = {{i, j}: (V_{i}, V_{j}) is (ε, q)-regular ∧ e_{F} (V_{i}, V_{j}) ≥ αqm^{2}}.

Our next aim is to apply the classical Turán theorem to guarantee the existence of a K_{l} ⊆ F_{cluster}. For this we define a subgraph F′ of F. Set

E(F′) = ⋃{E_{F} (V_{i}, V_{j}): {i, j} ∈ E(F_{cluster})}

We now want to find a lower bound for |E(F′)|. There are four possible reasons for an edge e ∈ E(F) not to be in E(F′):

(R1) e has at least one vertex in V_{0}, (R2) e is contained in some vertex class V_{i} for 1 ≤ i ≤ t, (R3) e is in E(V_{i}, V_{j}) for an (ε, q)-irregular pair (V_{i}, V_{j}), or (R4) e is in E(V_{i}, V_{j}) for sparse a pair (i.e., e(V_{i}, V_{j}) < αqm^{2}).

We bound the number of discarded edges of type (R1)–(R3) by applying that G is (ξ, C)- bounded (Property (P2)):

# of edges of type (R1) ≤ Cqεn^{2},
# of edges of type (R2) ≤ Cq (\frac{n}{t})^{2} · t,
# of edges of type (R3) ≤ Cq (\frac{n}{t})^{2} · ε\binom{t}{2}.

Furthermore, we bound the number of discarded edges of type (R4), by

# of edges of type (R4) ≤ αq (\frac{n}{t})^{2} · \binom{t}{2}.

This, combined with n ≥ 2, (11), (13), (14), (15), and δ < 1 implies that

|E(F) \ E(F′)| ≤ (C (ε + \frac{1}{t} + \frac{ε}{2}) + \frac{α}{2}) qn^{2}
≤ (C (2ε + \frac{1}{t}) + \frac{α}{2}) · 4q\binom{n}{2}
≤ ((4 + δ) (\frac{δ}{40} + \frac{δ}{40}) + \frac{δ}{4}) q\binom{n}{2} ≤ \frac{δ}{2}q\binom{n}{2},

and thus

|E(F′)| ≥ (1 − \frac{1}{l − 1} + \frac{δ}{2}) q\binom{n}{2}.

We use the last inequality and once again (P2) to achieve the desired lower bound for |E(F_{cluster})|. Indeed,

|E(F_{cluster})| ≥ \frac{e(F′)}{Cq(n/t)^{2}} = (1 − \frac{1}{l − 1} + \frac{δ}{2}) (1 − \frac{1}{n}) (1 + \frac{δ}{4})^{−1} \frac{t^{2}}{2} ,

and then, for n large enough (n > 16/δ^{2}), by using t^{2} ≥ 8l^{2}/δ, we deduce that

|E(F_{cluster})| > (1 − \frac{1}{l − 1} + \frac{δ}{2}) (1 − \frac{δ}{4}) \frac{t^{2}}{2}
≥ (1 − \frac{1}{l − 1} + \frac{δ}{8}) \frac{t^{2}}{2}  (16)
≥ (1 − \frac{1}{l − 1}) \frac{t^{2}}{2} + \frac{l^{2}}{2} .

The last inequality implies, by Turán’s theorem [18], that there is a subgraph K_{l} in F_{cluster}. Let {i_{1}, …, i_{l}} be the vertex set of this K_{l} in F_{cluster}. Then we set J_{0} = F [V_{i_{1}}, …, V_{i_{l}}] ⊆ F. Now, every pair (V_{i_{j}}, V_{i_{j′}}) for 1 ≤ j < j′ ≤ l satisfies the conditions of Lemma 3.4 with ε^{Lem3.4} = ε and α^{Lem3.4} = α. Thus there is a subgraph J ⊆ J_{0} ⊆ F that is (3ε, q)-regular and e_{J}(V_{i_{j}}, V_{i′_{j}}) = αqm^{2}. Since ε ≤ ε^{CL}/3 and J satisfies conditions (I)–(IV) of the Counting Lemma, Lemma 2.3, with the constants chosen above (α^{CL} = α, σ^{CL} = σ, and ε^{CL} ≥ 3ε), there are at least

(1 − σ)p^{\binom{l}{2}}m^{l} = \frac{(1 − σ)α^{\binom{l}{2}}}{t^{l}} q^{\binom{l}{2}}n^{l} ≥ \frac{(1 − σ)α^{\binom{l}{2}}}{(T_{0}^{SRL})^{l}} q^{\binom{l}{2}}n^{l}

different copies of K_{l} in J ⊆ F. Observe that α, σ and T_{0} depend on δ and l but not on n. Consequently, there are c(δ, l)q^{\binom{l}{2}}n^{l} ≫ 1 (where c(δ, l) = (1 − σ)α^{\binom{l}{2}}/ (T_{0}^{SRL})^{l}) copies of K_{l} in F, as required by Theorem 1.2.

4. The counting lemma

Our aim in this section is to prove Lemma 2.3. In order to do this, we will need two lemmas. We introduce these in the first two subsections. Then, in Section 4.3, we will illustrate the proof of the Counting lemma on the particular case l = 4. Finally, we give the proof of Lemma 2.3 in Section 4.4.

4.1. The pick-up lemma Before we state the ‘Pick-Up Lemma’, Lemma 4.3, let us state a simple one-sided estimate for the hypergeometric distribution, which will be useful in the proof of Lemma 4.3.

Lemma 4.1 (A hypergeometric tail lemma). Let b, d, and u be positive integers and suppose we select a d-set D uniformly at random from a set U of cardinality u. Suppose also that we are given a fixed b-set B ⊆ U. Then we have for λ > 0

ℙ (|D ∩ B| ≥ λ\frac{bd}{u}) ≤ (\frac{e}{λ})^{λbd/u} .  (17)

Proof. For the proof we refer the reader to [11].

We now state and prove the Pick-Up Lemma. Let k ≥ 2 be a fixed integer and let m be sufficiently large. Let V_{1}, …, V_{k} be pairwise disjoint sets all of size m and let B be a subset of V_{1} × ⋯ × V_{k}. For 1 > p = p(m) ≫ 1/m set T = pm^{2} and consider the probability space

Ω = \binom{V_{1} × V_{k}}{T} × ⋯ × \binom{V_{k−1} × V_{k}}{T},

where \binom{V_{i}×V_{k}}{T} denotes the family of all subsets of V_{i} × V_{k} of size T, and all the R = (R_{1}, …, R_{k−1}) ∈ Ω are equiprobable, i.e., have probability

\binom{m^{2}}{T}^{−(k−1)}.

For every R = (R_{1}, …, R_{k−1}) ∈ Ω the degree with respect to R_{i} (1 ≤ i < k) of a vertex v_{k} in V_{k} is

d_{R_{i}}(v_{k}) = |{v_{i} ∈ V_{i}: (v_{i}, v_{k}) ∈ R_{i}}|.  (18)

Definition 4.2 (Π(ζ, μ, K)). For ζ, μ, K with 1 > ζ, μ > 0 and K > 0, we say that property Π(ζ, μ, K) holds for R = (R_{1}, …, R_{k−1}) ∈ Ω if

Ṽ_{k} = Ṽ_{k}(K) = {v_{k} ∈ V_{k}: d_{R_{i}}(v_{k}) ≤ Kpm, ∀1 ≤ i ≤ k − 1}

and

B(R) = {b = (v_{1}, …, v_{k}) ∈ B: v_{k} ∈ Ṽ_{k} ∧ (v_{j}, v_{k}) ∈ R_{j}, ∀ 1 ≤ j ≤ k − 1}

satisfy the inequalities

|Ṽ_{k}| ≥ (1 − μ)m,  (19)
|B(R)| ≤ ζp^{k−1}m^{k}.  (20)

We think of B(R) as the members of B that have been picked-up by the random element R ∈ Ω. We will be interested in the probability that the property Π(ζ, μ, K) fails for a fixed B in the uniform probability space Ω.

Lemma 4.3 (Pick-Up Lemma). For every β, ζ and μ with 1 > β, ζ, μ > 0 there exist 1 > η = η(β, ζ, μ) > 0, K = K(β, μ) > 0 and m_{0} such that if m ≥ m_{0} and

|B| ≤ ηm^{k},  (21)

then

ℙ(Π(ζ, μ, K) fails for R ∈ Ω) ≤ β^{(k−1)T} .  (22)

For the proof we need a few definitions. Suppose β and μ are given. We define

θ = \frac{1}{2}β^{k−1},  (23)
K = max \{\frac{3(k − 1) log 1/θ}{μ} , e^{2}\} .  (24)

Since p ≫ 1/m the definition of K ≥ 3(k − 1) log(1/θ)/μ implies that

(k − 1)\binom{m}{μm/(k − 1)} exp (−\frac{μT K log K}{2(k − 1)} ) ≤ θ^{T}  (25)

holds for m sufficiently large.

Using the definition of d_{R_{i}} in (18) we construct for each i = 1, …, k − 1 a subset of V_{k} by putting

V_{k}^{(i)} = {v_{k} ∈ V_{k}^{(i−1)} : d_{R_{i}}(v_{k}) ≤ Kpm},

where V_{k}^{(0)} = V_{k}. Observe that V_{k} = V_{k}^{(0)} ⊇ V_{k}^{(1)} ⊇ ⋯ ⊇ V_{k}^{(k−1)} = Ṽ_{k}. In the view of Lemma 4.3 we define the following “bad” events in Ω.

Definition 4.4 (A_{i}, B). For each i = 0, …, k − 1 and K, μ > 0, ζ > 0, let A_{i} = A_{i}(μ, K), B = B(ζ, K) ⊆ Ω be the events

\begin{aligned}A_{i}: & |V_{k}^{(i)}| & < & (1 − iμ/(k − 1))m, \\ B: & |B(R)| & > & ζp^{k−1}m^{k}. \end{aligned}

Observe that the definition of V_{k}^{(0)} = V_{k} implies

ℙ(A_{0}) = 0.  (26)

We restate Lemma 4.3 by using the notation introduced in Definition 4.4.

Lemma 4.3′ (Pick-up Lemma, event version). For every β, ζ and μ with 1 > β, ζ, μ > 0 there exist 1 > η = η(β, ζ, μ) > 0, K = K(β, μ) > 0 and m_{0} such that if m ≥ m_{0} and

|B| ≤ ηm^{k},  (27)

then

ℙ(A_{k−1}(μ, K) ∨ B(ζ, K)) ≤ β^{(k−1)T} .  (28)

We need some more preparation before we prove Lemma 4.3′. Suppose β, ζ, μ are given by Lemma 4.3′ and θ, K are fixed by (23) and (24). For each i = 1, …, k − 1 we consider the set B_{i} ⊆ B consisting of those k-tuples b ∈ B which were partially “picked up” by edges of R_{1}, …, R_{i}. For technical reasons we consider only those k-tuples containing vertices v_{k} ∈ V_{k}^{(i−1)}, i.e., with d_{R_{j}}(v_{k}) ≤ Kpm for j = 1, …, i − 1. More formally, we let

B_{i} = {b = (v_{1}, …, v_{k}) ∈ B: v_{k} ∈ V_{k}^{(i−1)} ∧ (v_{j}, v_{k}) ∈ R_{j}, ∀ 1 ≤ j ≤ i}.

We also set B_{0} = B.

The definitions of Ṽ_{k} = V_{k}^{(k−1)} ⊆ V_{k}^{(k−2)} and B_{k−1} imply

B(R) ⊆ B_{k−1}.  (29)

(Equality may fail in (29) because we may have V_{k}^{(k−2)}\V_{k}^{(k−1)} ≠ ∅.) For each i = k, …, 1 define ζ_{i−1} by

ζ_{k−1} = ζ,
ζ_{i−1} = \frac{k − 1 − (i − 1)μ}{4(k − 1)K^{i−1}}ζ_{i}^{2}θ^{4K^{i−1}/ζ_{i}}.  (30)

Furthermore, consider for each i = 0, …, k − 1 the event B_{i} = B_{i}(ζ_{i}, K) ⊆ Ω defined by

B_{i}: |B_{i}| > ζ_{i}p^{i}m^{k}.  (31)

In order to prove Lemma 4.3′ we need two more claims, which we will prove later.

Claim 4.5. For all 1 ≤ i ≤ k − 1, we have

ℙ(A_{i}) = ℙ (|V_{k}^{(i)}| < (1 − \frac{iμ}{k − 1}) m) ≤ θ^{T} .

Claim 4.6. For all 1 ≤ i ≤ k − 1, we have

ℙ(B_{i} | ¬A_{i−1} ∧ ¬B_{i−1}) ≤ θ^{T} .

Assuming Claims 4.5 and 4.6, we may easily prove Lemma 4.3′.

Proof of Lemma 4.3′. Set η = ζ_{0} where ζ_{0} is given by (30). The definition of B_{0} = B and (27) implies |B_{0}| ≤ ζ_{0}m^{k} and consequently by the definition of the event B_{0} in (31)

ℙ(B_{0}) = 0.  (32)

Because of (29) and ζ_{k−1} = ζ in (30) we have

ℙ(B) ≤ ℙ(B_{k−1}).  (33)

Using the formal identity

ℙ(B_{i}) = ℙ(B_{i} ∧ (¬A_{i−1} ∧ ¬B_{i−1})) + ℙ(B_{i} ∧ (A_{i−1} ∨ B_{i−1})),

we observe that

ℙ(B_{i}) ≤ ℙ(B_{i} | ¬A_{i−1} ∧ ¬B_{i−1}) + ℙ(A_{i−1}) + ℙ(B_{i−1})  (34)

16 Y. Kohayakawa, V. Rödl, and M. Schacht for each i = 1, …, k − 1. It follows by applying (33) and (34) that

ℙ(A_{k−1} ∨ B) ≤ ℙ(A_{k−1}) + ℙ(B_{k−1})

≤ ℙ(A_{k−1}) + ∑_{i=1}^{k−1} (ℙ(B_{i} | ¬A_{i−1} ∧ ¬B_{i−1}) + ℙ(A_{i−1})) + ℙ(B_{0}).

Claims 4.5 and 4.6, and (26), (32) and (23) finally imply

ℙ(A_{k−1} ∨ B) ≤ 2(k − 1)θ^{T} ≤ 2(k − 1) (\frac{β^{k−1}}{2} )^{T} ≤ β^{(k−1)T}

for m sufficiently large, as required.

We now prove Claim 4.5 and then Claim 4.6. Proof of Claim 4.5. Fix a set V^{∗} ⊆ V_{k} of size μm/(k − 1). For a fixed j (1 ≤ j ≤ i) assume that d_{R_{j}}(v_{k}) > Kpm for every v_{k} in V^{∗}. This clearly implies the event

E_{j}(V^{∗}): |R_{j} ∩ (V_{j} × V^{∗})| > Kpm\frac{μm}{k − 1} = K \frac{μT}{k − 1}.  (35)

The T pairs of R_{j} are chosen uniformly in V_{j} × V_{k}, so the hypergeometric tail lemma, Lemma 4.1, applies, and using the fact that e ≤ K^{1/2} by (24) we get

ℙ (E_{j}(V^{∗})) ≤ (\frac{e}{K} )^{KμT /(k−1)} ≤ exp (−\frac{μT K log K}{2(k − 1)} ) .  (36)

Set E_{j} = ⋁ E_{j}(V^{∗}), where the union is taken over all V^{∗} ⊆ V_{k} of size μm/(k − 1). Then

ℙ(E_{j}) ≤ \binom{m}{μm/(k − 1)} exp (−\frac{μT K log K}{2(k − 1)} )  (37)

holds for each j = 1, …, i, and this implies

ℙ( ⋁_{j=1}^{i} E_{j}) ≤ i\binom{m}{μm/(k − 1)} exp (−\frac{μT K log K}{2(k − 1)} ) .

Finally, the fact that A_{i} ⊆ ⋁_{j=1}^{i} E_{j} and the choice of K with (25) gives that

ℙ(A_{i}) ≤ i\binom{m}{μm/(k − 1)} exp (−\frac{μT K log K}{2(k − 1)} ) ≤ θ^{T} ,

as required. Proof of Claim 4.6. Recall β, ζ and μ are given by Lemma 4.3′ and θ, K and ζ_{i} are fixed by (23), (24) and (30). In order to prove Claim 4.6 we fix i (1 ≤ i ≤ k − 1) and we assume ¬A_{i−1} and ¬B_{i−1} occur. This means by Definition 4.4 and (31) that

|V_{k}^{(i−1)}| ≥ (1 − \frac{(i − 1)μ}{k − 1}) m = (\frac{k − 1 − (i − 1)μ}{k − 1}) m,  (38)
|B_{i−1}| ≤ ζ_{i−1}p^{i−1}m^{k}.  (39)

We have to show that

|B_{i}| ≤ ζ_{i}p^{i}m^{k}  (40)

holds for R in the uniform probability space Ω with probability ≥ 1 − θ^{T}.

First we define the auxiliary constant

L_{i} = (\frac{1}{θ})^{4K^{i−1}/ζ_{i}} .  (41)

The definition of θ in (23) and the facts that 0 < ζ_{i} < 1 for each i = 1, …, k − 1 and K > 1 imply that

L_{i} ≥ (\frac{2}{β^{k−1}} )^{4} > e^{2}  (42)

holds.

We define the degree of a pair in V_{i} × V_{k}^{(i−1)} with respect to B_{i−1} by

d_{B_{i−1}}(w_{i}, w_{k}) = |{b = (v_{1}, …, v_{k}) ∈ B_{i−1} : v_{i} = w_{i} and v_{k} = w_{k}}|.

We can bound the value of the average degree by (38) and (39):

avg \{d_{B_{i−1}}(v_{i}, v_{k}): (v_{i}, v_{k}) ∈ V_{i} × V_{k}^{(i−1)}\} = \frac{|B_{i−1}|}{m|V_{k}^{(i−1)}|}  (43)

≤ \frac{k − 1}{k − 1 − (i − 1)μ}ζ_{i−1}p^{i−1}m^{k−2}.

We also can bound Δ_{B_{i−1}}(V_{i}, V_{k}^{(i−1)}) = max{d_{B_{i−1}}(v_{i}, v_{k}): (v_{i}, v_{k}) ∈ V_{i} × V_{k}^{(i−1)}} by the following observation. Let (v_{i}, v_{k}) be an arbitrary element in V_{i} × V_{k}^{(i−1)}. Then, by the definition of V_{k}^{(i−1)}, we have

d_{B_{i−1}}(v_{i}, v_{k}) ≤ d_{R_{1}}(v_{k}) · . . . · d_{R_{i−1}}(v_{k}) · m^{k−2−(i−1)} ≤ (Kpm)^{i−1}m^{k−i−1}.  (44)

Inequality (44) implies

Δ_{B_{i−1}} (V_{i}, V_{k}^{(i−1)}) ≤ K^{i−1}p^{i−1}m^{k−2}.  (45)

Let F be the set of pairs of “high degree”. More precisely, set

F = \{(v_{i}, v_{k}) ∈ V_{i} × V_{k}^{(i−1)} : d_{B_{i−1}} > \frac{ζ_{i}}{2} p^{i−1}m^{k−2}\} .

A simple averaging argument applying (43) yields

|F | ≤ \frac{2(k − 1)ζ_{i−1}}{(k − 1 − (i − 1)μ)ζ_{i}} |V_{i}||V_{k}^{(i−1)}| ≤ \frac{2(k − 1)ζ_{i−1}}{(k − 1 − (i − 1)μ)ζ_{i}} m^{2}.  (46)

On the other hand, if we set F̄ = V_{i} × V_{k}^{(i−1)} \ F then the definition of F and (45) imply

|B_{i}| = ∑_{(v_{i},v_{k})∈R_{i}∩F̄} d_{B_{i−1}}(v_{i}, v_{k}) + ∑_{(v_{i},v_{k})∈R_{i}∩F} d_{B_{i−1}}(v_{i}, v_{k})

≤ \frac{ζ_{i}}{2} p^{i−1}m^{k−2}|R_{i} ∩ F̄| + K^{i−1}p^{i−1}m^{k−2}|R_{i} ∩ F |
≤ \frac{ζ_{i}}{2} p^{i−1}m^{k−2}T + K^{i−1}p^{i−1}m^{k−2}|R_{i} ∩ F |
= (\frac{ζ_{i}}{2} + \frac{K^{i−1}}{T} |R_{i} ∩ F |) p^{i}m^{k}.  (47)

Next we prove that

ℙ (|R_{i} ∩ F | > \frac{ζ_{i}T}{2K^{i−1}} ) ≤ θ^{T} ,  (48)

which, together with (47), yields our claim, namely, that

ℙ (|B_{i}| > ζ_{i}p^{i}m^{k}) ≤ θ^{T} .  (49)

We now prove inequality (48). Without loss of generality we assume equality holds in (46). Then the hypergeometric tail lemma, Lemma 4.1, implies that

ℙ (|R_{i} ∩ F | > L_{i} \frac{|F |T}{m^{2}} ) = ℙ (|R_{i} ∩ F | > L_{i} \frac{2(k − 1)ζ_{i−1}}{(k − 1 − (i − 1)μ)ζ_{i}} T )

≤ (\frac{e}{L_{i}} )^{L_{i} \frac{2(k−1)ζ_{i−1}}{(k−1−(i−1)μ)ζ_{i}} T}  (50)

≤ exp (−\frac{L_{i}(log L_{i})(k − 1)ζ_{i−1}T}{(k − 1 − (i − 1)μ)ζ_{i}} ) ,

where in the last inequality we used that L_{i} ≥ e^{2} (see (42)). The definitions of ζ_{i−1} and L_{i} in (30) and (41) yield

\frac{L_{i}(k − 1)ζ_{i−1}}{(k − 1 − (i − 1)μ)ζ_{i}} = \frac{L_{i}ζ_{i}}{4K^{i−1}} θ^{4K^{i−1}/ζ_{i}} = \frac{ζ_{i}}{4K^{i−1}} .

We use the last inequality to derive

\frac{L_{i}(log L_{i})(k − 1)ζ_{i−1}}{(k − 1 − (i − 1)μ)ζ_{i}} = log \frac{1}{θ},
L_{i} \frac{2(k − 1)ζ_{i−1}}{(k − 1 − (i − 1)μ)ζ_{i}} = \frac{ζ_{i}}{2K^{i−1}} ,

which, combined with inequality (50), gives (48).

4.2. The k-tuple lemma for subgraphs of random graphs Let G ∈ G(n, q) be the binomial random graph with edge probability q = q(n), and suppose H = (U, W; F) is a bipartite, not necessarily induced subgraph of G with |U| = m_{1} and |W | = m_{2}. Furthermore, denote the density of H by p = e(H)/m_{1}m_{2}.

We now consider subsets of W of fixed cardinality k ≥ 1, and classify them according to the size of their joint neighbourhood in H. For this purpose we define

B^{(k)}(U, W; γ) = {b = {v_{1}, …, v_{k}} ∈ W: |d_{U}^{H}(b) − p^{k}m_{1}| ≥ γp^{k}m_{1}} ,

where d_{U}^{H}(b) denotes the size of the joint neighbourhood of b in H, that is,

d_{U}^{H}(b) = |⋂_{i=1}^{k} Γ_{H}(v_{i})| .

The following lemma states that in a typical G ∈ G(n, q) the set B^{(k)}(U, W; γ) is “small” for any sufficiently large (ε, q)-regular subgraph H = (U, W; F) of a dense enough random graph G. Recall that if G is a graph and U, W ⊂ V (G) are two disjoint sets of vertices, then G[U, W] denotes the bipartite graph naturally induced by (U, W).

Lemma 4.7 (The k-tuple lemma). For any constants α > 0, γ > 0, η > 0, and k ≥ 1 and function m_{0} = m_{0}(n) such that q^{k}m_{0} ≫ (log n)^{4}, there exists a constant ε > 0 for which the random graph G ∈ G(n, q) satisfies the following property with probability 1 − o(1): If for a bipartite subgraph H = (U, W; F) of G the conditions (i ) e(H) ≥ αe(G[U, W]), (ii ) H is (ε, q)-regular, (iii ) |U| = m_{1} ≥ m_{0} and |W | = m_{2} ≥ m_{0} apply, then

|B^{(k)}(U, W; γ)| ≤ η\binom{m_{2}}{k}  (51)

also applies.

Proof. The proof of Lemma 4.7 is given in [11].

4.3. Outline of the proof of the counting lemma for l = 4 The proof of the Lemma 2.3 contains some technical definitions. In order to make the reading more comprehensible, we first informally illustrate the basic ideas of the proof for the case l = 4, before we give the proof for a general l ≥ 2 in Section 4.4.

Consider the following situation: Let V_{1}, V_{2}, V_{3}, and V_{4} be pairwise disjoint sets of vertices of size m. Let J be a 4-partite graph with vertex set V (J) = V_{1} ∪ V_{2} ∪ V_{3} ∪ V_{4}. We think of J as a not necessarily induced subgraph of a random graph in G(n, q) with T = pm^{2} edges between each V_{i} and V_{j} (1 ≤ i < j ≤ 4), where p = αq. We will describe a situation in which we will be able to assert that J contains the “right” number of K_{4}’s. Here and everywhere below by the “right” number we mean “as expected in a random graph of density p”; notice that, for the number of K_{4}’s, this means ∼ p^{6}m^{4}. Observe that, however, J is a not necessarily induced subgraph of a graph in G(n, q), and this makes our task hard. As it turns out, it will be more convenient to imagine that J is generated in l − 1 = 3 stages. First we choose the edges from V_{4} to V_{1} ∪ V_{2} ∪ V_{3}. Then we choose the edges from V_{3} to V_{1} ∪ V_{2}, and in the third stage we disclose the edges between V_{2} and V_{1}.

The key idea of the proof is to consider “bad” tuples, which we create in every stage.

“bad” 3-tuples  (b) (a)  discarded vertices 3-tuple  neighbours v_{3} such that (v_{1}, v_{2}, v_{3}) is not a “bad” 3-tuple approxiametly expected number of joint (i) (ii) Pair (v_{1}, v_{2}) is good if it has: “picked-up”  V_{3} V_{1} V_{2}  v_{2}  v_{3} v_{1} Ṽ_{3}

Figure 1

After we chose the edges from V_{4} to the other vertex classes, we define “bad” 3-tuples in V_{1} × V_{2} × V_{3}: a 3-tuple is “bad” if its joint neighbourhood in V_{4} is much smaller than expected. Then, with the right choice of constants, Proposition 4.11 for k = 3 and J = J[V_{4}, V_{1} ∪ V_{2} ∪ V_{3}] will ensure that there are not too many “bad” 3-tuples. (Proposition 4.11 is a corollary of the the k-tuple lemma, Lemma 4.7.)

We next generate the edges between V_{3} and V_{1} ∪ V_{2}. We want to define “bad” pairs in V_{1} × V_{2}. Here it becomes slightly more complicated to distinguish “bad” from “good”. This is because there are two things that might go wrong for a pair in V_{1} × V_{2}. First of all, again the joint neighbourhood (now in V_{3}) of a pair in V_{1} × V_{2} might be too small. On the other hand, it could have the right number of joint neighbours in V_{3}, but many of these neighbours “complete” the pair to a “bad” 3-tuple. Here the Pick-Up Lemma comes into play for k = 3 (see Proposition 4.10): this lemma will ensure that, given the set of “bad” 3-tuples (which was already defined in the first stage) is small, we will not “pick-up” too many of these (see Figure 1(a)), while choosing the edges between V_{3} and V_{1} ∪ V_{2}. (We say that a triple (v_{1}, v_{2}, v_{3}) has been picked-up if (v_{1}, v_{3}) and (v_{2}, v_{3}) are in the edge set generated between V_{3} and V_{1} ∪ V_{2}.)

Here the situation complicates somewhat. The Pick-Up Lemma forces us to discard a small portion (less or equal μ^{PU} fraction) of vertices in V_{3}. Thus, in order to avoid the first type of “badness” (too small joint neighbourhood) as a 2-tuple in V_{1} × V_{2} it is not enough to have the right number of joint neighbours in V_{3}; we need the right number of joint neighbours in Ṽ_{3}, which is V_{3} without the μ^{PU}m vertices (at most) we lose by applying the Pick-Up Lemma (see Figure 1(b)). This will be ensured by the the k-tuple lemma (to be more precise, Proposition 4.11), now for k = 2 and J = J[Ṽ_{3}, V_{1} ∪ V_{2}].

Later, in the general case, we will refer to the set of “bad” i-tuples in V_{1} × ⋯ × V_{i} as B_{i} (see Definition 4.8 below). We define B_{i} as the union of the sets B_{i}^{(a)} and B_{i}^{(b)}, defined as follows. We put in B_{i}^{(a)} the i-tuples that are “bad” because they have a joint neighbourhood in Ṽ_{i+1} that is too small; the set B_{i}^{(b)} is defined as the set of i-tuples in V_{1} × ⋯ × V_{i} that “bad” because they extend to too many “bad” (i + 1)-tuples (i.e., (i + 1)-tuples in B_{i+1}).

As described above, we define B_{i} (i = l − 1, …, 1) by reverse induction, starting with B_{l−1}, and going down to B_{1}. With the right choice of constants, there will not be too many “bad” vertices in V_{1}.

Having ensured that most of the m vertices in V_{1} are not “bad” (i.e., do not belong to B_{1}) we are now able to count the number of K_{4}’s. We will use the following deterministic argument, which will later be formalized in Lemma 4.13. Consider a vertex v_{1} in V_{1} that is not “bad”. This vertex has approximately the expected number of neighbours in Ṽ_{2} (i.e., ∼ pm), and not too many of these neighbours constitute, together with v_{1}, a “bad” 2tuple. In other words, this means that v_{1} extends to ∼ pm copies of K_{2} in (V_{1} × V_{2}) \ B_{2}. This implies that each such K_{2} has the right number of joint neighbours in Ṽ_{3} (i.e., ∼ p^{2}m), and consequently extends to the right number of K_{3}’s in (V_{1} × V_{2} × V_{3}) \ B_{3}. Repeating the last argument, each of these K_{3}’s extends into ∼ p^{3}m different copies of K_{4}. Since we have ensured that most of the m vertices in V_{1} are not “bad”, we have ∼ m · pm · p^{2}m · p^{3}m = p^{\binom{4}{2}}m^{4} copies of K_{4}.

4.4. Proof of the counting lemma In this section we will prove Lemma 2.3. In the section ‘Concepts and Constants’, we introduce the key definitions and describe the logic of all important constants which will appear later in the proof. Afterwards we prove two technical propositions in the section ‘Tools’. These propositions correspond to the lemmas in Sections 4.1 and 4.2, and their use will give a short proof of the Counting Lemma, to be presented in the section ‘Main proof’.

Concepts and constants. Let t ≥ l ≥ 2 be fixed integers and let n be sufficiently large. Let α and ε be positive constants. Let G ∈ G(n, q) be the binomial random graph with edge probability q = q(n), and suppose J is an l-partite subgraph of G with vertex classes V_{1}, …, V_{l}. For all 1 ≤ i < j ≤ l we denote by J_{ij} the bipartite graph induced by V_{i} and V_{j}. Consider the following assertions for J. (I) |V_{i}| = m = n/t for all 1 ≤ i ≤ l, (II) q^{l−1}n ≫ (log n)^{4}, (III) J_{ij} (1 ≤ i < j ≤ l) has T = pm^{2} edges, where 1 > αq = p ≫ 1/n, and (IV) J_{ij} (1 ≤ i < j ≤ l) is (ε, q)-regular. Let σ > 0 be given. We define the constants

γ = μ = ν = \frac{1}{3} (1 − (1 − σ)^{1/l}) ,  (52)

and, for 1 ≤ i ≤ l − 2, we put

β_{i+1} = (\frac{1}{2} (\frac{α}{e})^{\binom{l}{2}−\binom{i}{2}})^{1/i} .  (53)

In order to prove Lemma 2.3 we need some definitions. These definitions always depend on a fixed subgraph J of our random graph G ∈ G(n, q) satisfying (I)–(IV). However, we will drop references to J because we want to simplify the notation (e.g., we write V_{i} instead of V_{i}^{J}). Also, for each i = 1, …, l we denote V_{1} × ⋯ × V_{i} by W_{i}.

In the proof we consider for a fixed J sets of “bad” i-tuples B_{i} ⊆ W_{i} (1 ≤ i ≤ l − 1). We define these sets recursively from B_{l−1} to B_{1}. As mentioned above in the discussion of the l = 4 case, there are two reasons that make a given i-tuple in W_{i} “bad”. First of all, its joint neighbourhood in V_{i+1} might be too small (see the definition of B_{i}^{(a)} in Definition 4.8) and, secondly, it could extend into too many “bad” (i + 1)-tuples in B_{i+1} (see the definition of B_{i}^{(b)} in Definition 4.8). Note that the “bad” (i + 1)-tuples have already been defined, as we are using reverse induction in these definitions.

Next we apply the Pick-Up Lemma for k = i + 1 (1 ≤ i ≤ l − 2) with μ_{i+1}^{PU} = μ and β_{i+1}^{PU} = β_{i+1} (and yet unspecified ζ_{i+1}^{PU}). As a result we obtain K_{i+1}^{PU} = K_{i+1}^{PU}(β_{i+1}^{PU}, μ_{i+1}^{PU}) and the set

Ṽ_{i+1} = Ṽ_{i+1}^{PU}(K_{i+1}^{PU}) ⊆ V_{i+1}

of undiscarded vertices with

|Ṽ_{i+1}| ≥ (1 − μ)m.

We need a few more definitions before we define B_{i}, B_{i}^{(a)} and B_{i}^{(b)} (recursively for i = l − 1, …, 1). Let Γ̃_{i+1}(b) be the joint neighbourhood of b = (v_{1}, …, v_{i}) ∈ W_{i} in Ṽ_{i+1} with respect to J, more precisely

Γ̃_{i+1}(b) = {w ∈ Ṽ_{i+1} : (v_{j}, w) ∈ E(J_{j,i+1}), ∀ 1 ≤ j ≤ i}.

For a fixed set B ⊆ W_{i+1} and b = (v_{1}, …, v_{i}) ∈ W_{i} we denote the degree d_{B}(b) of b in B with respect to J by

d_{B}(b) = |{w ∈ Γ̃_{i+1}(b): (v_{1}, …, v_{i}, w) ∈ B}| .

Next we define (still for a fixed J) the sets of “bad” i-tuples B_{i} = B_{i}(γ, μ, ν) ⊆ W_{i} mentioned earlier. Although we do not apply the Pick-Up Lemma for k = l, for the sake of convenience we consider the neighbourhood of elements in W_{l−1} in Ṽ_{l}, instead of in V_{l}.

Definition 4.8 (B_{l−1}, B_{i}^{(a)}, B_{i}^{(b)}, B_{i}). Let γ, μ, ν be given by (52). We define recursively the following sets of “bad” tuples for i = l − 1, …, 1:

\begin{aligned}B_{l−1} & = & B_{l−1}(γ, μ) & = & \{b ∈ W_{l−1} : |Γ̃_{l}(b)| < (1 − γ − μ)p^{l−1}m\} , \\ B_{i}^{(a)} & = & B_{i}^{(a)}(γ, μ) & = & \{b ∈ W_{i}: |Γ̃_{i+1}(b)| < (1 − γ − μ)p^{i}m\} , \\ B_{i}^{(b)} & = & B_{i}^{(b)}(ν) & = & \{b ∈ W_{i}: d_{B_{i+1}}(b) ≥ νp^{i}m\} , \\ B_{i} & = & B_{i}(γ, μ, ν) & = & B_{i}^{(a)}(γ, μ) ∪ B_{i}^{(b)}(ν). \end{aligned}

We also consider “bad” events in G(n, q) defined on the basis of the size of the sets B_{l−1}(γ, μ), B_{i}^{(a)}(γ, μ), B_{i}^{(b)}(ν), and B_{i}(γ, μ, ν) defined above. In the following definition we mean by J an arbitrary subgraph of G ∈ G(n, q) satisfying conditions (I)–(IV).

Definition 4.9. Let γ, μ, ν be given by (52) and let η_{i} > 0 (i = l − 1, …, 1) be fixed. We define the events

X_{l−1}(γ, μ, η_{l−1}): ∃ J ⊆ G s.t. |B_{l−1}| > (η_{l−1}/2)m^{l−1},
X_{i}^{(a)}(γ, μ, η_{i}): ∃ J ⊆ G s.t. |B_{i}^{(a)}| > (η_{i}/2)m^{i},
X_{i}^{(b)}(γ, μ, ν, η_{i}, η_{i+1}): ∃ J ⊆ G s.t. |B_{i+1}| ≤ η_{i+1}m^{i+1} ∧ |B_{i}^{(b)}| > (η_{i}/2)m^{i},
X_{i}(γ, μ, ν, η_{i}, η_{i+1}) = X_{i}^{(a)}(γ, μ, η_{i}) ∨ X_{i}^{(b)}(γ, μ, ν, η_{i}, η_{i+1}).

For simplicity, we let

X_{l−1}^{(a)} = X_{l−1} = X_{l−1}(γ, μ, η_{l−1}),
X_{i}^{(a)} = X_{i}^{(a)}(γ, μ, η_{i}) for i = 1, …, l − 1,
X_{i}^{(b)} = X_{i}^{(b)}(γ, μ, ν, η_{i}, η_{i+1}) for i = 1, …, l − 2,

and

X_{i} = X_{i}(γ, μ, ν, η_{i}, η_{i+1}) for i = 1, …, l − 1.

Owing to the special role of X_{1} later in the proof, we let

X_{bad} = X_{bad}(γ, μ, ν, η_{1}, η_{2}) = X_{1}(γ, μ, ν, η_{1}, η_{2}).

We will now describe the remaining constants used in the proof. Notice that α and σ were given and we have already fixed γ, μ, and ν in (52) and β_{i} for 2 ≤ i ≤ l − 1 in (53). The (yet unspecified) parameters η_{i} and ε will be determined by Propositions 4.10 and 4.11. First we set η_{1} = ν. Then Proposition 4.10 (PU_{i+1}) inductively describes η_{i+1} = η_{i+1}(β_{i+1}, γ, μ, ν, η_{i}) for i = 1, …, l − 2 such that ℙ(X_{i}^{(b)}) = o(1). Finally, for i = 1, …, l −1, Proposition 4.11 (TL_{i}) implies the choice for ε_{i} = ε_{i}(α, γ, μ, η_{i}) such that ℙ(X_{i}^{(a)}) = o(1). We set

ε = min{ε_{i}: i = 1, …, l − 1}.

A diagram illustrating the definition scheme for the constants above is given in Figure 2.

α, σ, γ, μ, ν, β_{2}, …, β_{l−1}

↓ η_{1} = ν ⟶^{PU_{2}} η_{2} ⟶ ⋯ ⟶ η_{i} ⟶^{PU_{i+1}} η_{i+1} ⟶ ⋯ ⟶^{PU_{l−1}} η_{l−1} ↓^{TL}_{1}  ↓  ↓^{TL}_{i}  ↓  ↓^{TL}_{l−1} ε_{1}  ε_{2}  …  ε_{i}  ε_{i+1}  …  ε_{l−1}

ε = min ε_{i}

Figure 2 Flowchart of the constants

Thus, ε is defined for any given α and σ, as claimed in Lemma 2.3. From now on, these constants are fixed for the rest of the proof of Lemma 2.3.

Tools. We need some auxiliary results before we prove Lemma 2.3. For this purpose we state variants of the Pick-Up Lemma, Lemma 4.3, and of the k-tuple lemma, Lemma 4.7, in the form that we apply these later. These variants will be referred to as (PU_{i+1}) and (TL_{i}).

The next proposition follows from Lemma 4.3 for k = i + 1 (1 ≤ i ≤ l − 2).

Proposition 4.10 (PU_{i+1}). Fix 1 ≤ i ≤ l − 2. Let α, σ > 0 be arbitrary, let γ, μ, ν and β_{i+1} be given by (52) and (53), and let η_{i} be defined as stated in Section 4.4 (see Figure 2). Then there exists η_{i+1} = η_{i+1}(β_{i+1}, γ, μ, ν, η_{i}) > 0 such that for every t ≥ l a random graph G in G(n, q) satisfies the following property with probability 1 − o(1): If J is a subgraph of G satisfying (I)–(IV) and B_{i+1}(γ, μ, ν) ⊆ W_{i+1} is such that

|B_{i+1}(γ, μ, ν)| ≤ η_{i+1}m^{i+1},  (54)

then the number of i-tuples b in W_{i} with

d_{B_{i+1}}(b) ≥ νp^{i}m

is less than

\frac{η_{i}}{2} m^{i},

which means

|B_{i}^{(b)}(ν)| ≤ \frac{η_{i}}{2} m^{i}.  (55)

Furthermore,

|Ṽ_{i+1}| ≥ (1 − μ)m

holds.

We restate Proposition 4.10, by using the events X_{i}^{(b)} from Definition 4.9. Observe that inequalities (54) and (55) correspond to X_{i}^{(b)}, so that ℙ(X_{i}^{(b)}) = o(1) is equivalent to the first part of Proposition 4.10′.

Proposition 4.10′ (PU_{i+1}). Fix 1 ≤ i ≤ l − 2. Let α, σ > 0 be arbitrary, let γ, μ, ν and β_{i+1} be given by (52) and (53), and let η_{i} be defined as stated in Section 4.4 (see Figure 2). Then there exists η_{i+1} = η_{i+1}(β_{i+1}, γ, μ, ν, η_{i}) > 0 such that for every t ≥ l

ℙ (X_{i}^{(b)}(γ, μ, ν, η_{i}, η_{i+1})) = o(1)

and

ℙ (|Ṽ_{i+1}| < (1 − μ)m) = o(1).

Proof. We apply Lemma 4.3 for k = i + 1 and with the following choice of β^{PU}, ζ^{PU}, μ^{PU}:

β^{PU} = β_{i+1},  (56)
ζ^{PU} = \frac{η_{i}ν}{2} ,  (57)
μ^{PU} = μ.  (58)

Lemma 4.3 then gives η^{PU}, from which we define the constant η_{i+1} we are looking for by putting

η_{i+1} = η^{PU}.

We assume inequality (54) holds. In other words, the number of the “bad” (i + 1)-tuples in W_{i+1} is

|B_{i+1}| ≤ η_{i+1}m^{i+1} = η^{PU}m^{i+1}.  (59)

On the other hand, if we assume that (55) does not hold (i.e., the event X_{i}^{(b)} occurs), then the number of (i + 1)-tuples in B_{i+1} that have been “picked-up” has to exceed

\frac{η_{i}}{2} m^{i} · νp^{i}m = ζ^{PU}p^{i}m^{i+1}.  (60)

The Pick-Up Lemma bounds the number of these configurations in

\binom{V_{1} × V_{i+1}}{T} × ⋯ × \binom{V_{i} × V_{i+1}}{T}

by

(β^{PU})^{iT} · \binom{m^{2}}{T}^{i} = (β_{i+1})^{iT} \binom{m^{2}}{T}^{i}.  (61)

We now estimate the number of all possible graphs J satisfying (I)–(IV) for which (59) holds but the number of members in B_{i+1} that have been “picked-up” exceeds (60). There are fewer than \binom{n}{m}^{l} different ways to fix the l vertex classes of J. Furthermore, observe that B_{i+1} is determined by all the edges in J_{jj′} (i < j′ ≤ l, 1 ≤ j < j′ ≤ l, which

gives \binom{l}{2} − \binom{i+1}{2} different pairs jj′). Thus we have at most \binom{m^{2}}{T}^{\binom{l}{2}−\binom{i+1}{2}} possibilities to determine B_{i+1}. This, combined with (61), (III), and (53), yields that

ℙ (X_{i}^{(b)}) ≤ \binom{n}{m}^{l}\binom{m^{2}}{T}^{\binom{l}{2}−\binom{i+1}{2}} · (β_{i+1})^{iT} \binom{m^{2}}{T}^{i} · q^{(\binom{l}{2}−\binom{i}{2})T}

≤ 2^{nl} (\frac{em^{2}q}{T} )^{(\binom{l}{2}−\binom{i}{2})T} (β_{i+1})^{iT} ≤ 2^{nl} ((\frac{e}{α})^{\binom{l}{2}−\binom{i}{2}} (β_{i+1})^{i})^{T} ≤ 2^{nl−T} .

Since l is fixed and T ≫ m = n/t, we have

ℙ (X_{i}^{(b)}) = o(1).

Note that the set Ṽ_{i+1} was determined by the application of the Pick-Up Lemma. Therefore, the second assertion in Proposition 4.10′ also follows from the proof above.

The following is an easy consequence of Lemma 4.7 for k = i (1 ≤ i ≤ l − 1).

Proposition 4.11 (TL_{i}). Fix 1 ≤ i ≤ l −1. Let α, σ > 0 be arbitrary, let γ, μ be given by (52), and let η_{i} be defined as stated in Section 4.4 (see Figure 2). Then there exists ε_{i} = ε_{i}(α, γ, μ, η_{i}) > 0 such that for every t ≥ l a random graph G in G(n, q) satisfies the following property with probability 1 − o(1): If ε ≤ ε_{i} and J is a subgraph of G satisfying (I)–(IV), then the number of i-tuples b in W_{i} with

|Γ̃_{i+1}(b)| < (1 − γ − μ)p^{i}m

is less than

\frac{η_{i}}{2} m^{i},

which means that

|B_{i}^{(a)}(γ, μ)| ≤ \frac{η_{i}}{2} m^{i}.  (62)

We can reformulate Proposition 4.11 in a shorter way by using the event X_{i}^{(a)} (see Definition 4.9).

Proposition 4.11′ (TL_{i}). Fix 1 ≤ i ≤ l − 1. Let α, σ > 0 be arbitrary, let γ, μ be given by (52) and let η_{i} be defined as stated in Section 4.4 (see Figure 2). Then there exists ε_{i} = ε_{i}(α, γ, μ, η_{i}) > 0 such that for every t ≥ l and ε ≤ ε_{i}

ℙ (X_{i}^{(a)}(γ, μ, η_{i})) = o(1).

Proof. We apply the k-tuple lemma, Lemma 4.7, with k = i, α^{TL} = α/3, γ^{TL} = γ and

η^{TL} = η_{i}/(2i^{i}).  (63)

The k-tuple lemma gives an ε^{TL} and we set ε_{i} = min{(ε^{TL})^{3} , α/2, 1/27}. Let ε ≤ ε_{i} and J be a subgraph of G ∈ G(n, q) satisfying (I)–(IV). Set U = Ṽ_{i+1} and W = ⋃_{j=1}^{i} V_{j}. By (IV), the graph J_{jj′} (1 ≤ j < j′ ≤ i) is (ε, q)-regular. A straightforward argument (using ε ≤ 1/27 and Lemma 3.2 for C = 3/2) shows that with probability 1 − o(1) the subgraph J[U, W] is at least (\sqrt[3]{ε}, q)-regular and therefore (ε^{TL}, q)-regular, which yields condition (ii) of Lemma 4.7. Moreover, with probability 1 − o(1) we have, say,

|E(G[U, W])| ≤ \frac{3}{2}q(1 − μ)km^{2},

and using the regularity of J we see that

|E(J[U, W])| ≥ (α − ε)q(1 − μ)km^{2},

which by our choice of ε gives condition (i) of Lemma 4.7. Finally, with assertion (II) for J all assumptions of the k-tuple lemma are satisfied for J[U, W].

Therefore, the k-tuple lemma implies that, with probability 1 − o(1), we have

|\{b ∈ W_{i}: |Γ̃_{i+1}(b)| ≤ (1 − γ)p^{i}(1 − μ)m\}| ≤ η^{TL}\binom{im}{i}.

The choice of η^{TL} in (63) gives

|\{b ∈ W_{i}: |Γ̃_{i+1}(b)| ≤ (1 − γ − μ + γμ)p^{i}m\}| ≤ \frac{η_{i}}{2} m^{i},

and hence (62) holds with probability 1 − o(1), by the simple observation that

|Γ̃_{i+1}(b)| ≤ (1 − γ − μ)p^{i}m implies |Γ̃_{i+1}(b)| ≤ (1 − γ − μ + γμ)p^{i}m.

Main proof. Our proof of the Counting Lemma, Lemma 2.3, follows immediately from Lemmas 4.12 and 4.13 below. Lemma 4.12 is a probabilistic statement and asserts that the probability of the event X_{bad} ⊆ G(n, q) is o(1). On the other hand, Lemma 4.13 is deterministic and claims that if a graph G is not in X_{bad} and J is a not necessarily induced subgraph of G satisfying (I)–(IV), then J contains the right number of copies of K_{l}. We apply the technical propositions from the last section in the proof of the probabilistic Lemma 4.12 below.

Lemma 4.12. For arbitrary α and σ > 0, let γ, μ, ν be given by (52), and let ε and η_{i} (i = 2, …, l − 1) be defined as stated in Section 4.4. Let G be a random graph in G(n, q). Then

ℙ(G ∈ X_{bad}(γ, μ, ν)) = o(1).

Proof. Formal logic implies

X_{bad} ⊆ X_{1}^{(a)} ∨ (X_{1}^{(b)} ∧ ¬X_{2}) ∨ X_{2}^{(a)} ∨ (X_{2}^{(b)} ∧ ¬X_{3})
∨ ⋮ ∨  ⋮
∨ X_{l−2}^{(a)} ∨ (X_{l−2}^{(b)} ∧ ¬X_{l−1}) ∨ X_{l−1},

and thus, by Propositions 4.10 and 4.11 (notice X_{l−1} = X_{l−1}^{(a)} by Definition 4.9), we have

ℙ (X_{bad}) ≤ ∑_{i=1}^{l−2} (ℙ(X_{i}^{(a)}) + ℙ(X_{i}^{(b)})) + ℙ(X_{l−1}) = o(1).

Lemma 4.13. For arbitrary α and σ > 0, let γ, μ, ν be given by (52), and let ε and η_{i} (i = 2, …, l − 1) be defined as stated in Section 4.4. Then every subgraph J of a graph G ∉ X_{bad}(γ, μ, ν) satisfying conditions (I)–(IV) contains at least

(1 − σ)p^{\binom{l}{2}}m^{l}

copies of K_{l}.

Proof. We shall prove by induction on i that the following statement holds for all 1 ≤ i ≤ l:

(S_{i}) Let J be a subgraph of G ∉ X_{bad} such that (I)–(IV) apply. Then there are at least

(1 − γ − μ − ν)^{i}p^{\binom{i}{2}}m^{i} different i-tuples in W_{i} \ B_{i} that induce a K_{i} in J[V_{1}, …, V_{i}]. Suppose i = 1. Note that ¬X_{bad} implies that |V_{1} ∩ B_{1}| ≤ η_{1}m = νm. Therefore V_{1} \ B_{1} contains at least (1 − ν)m ≥ (1 − γ − μ − ν)p^{0}m^{1} copies of K_{1}.

We now proceed to the induction step. Assume i ≥ 2 and (S_{i−1}) holds. Therefore, W_{i−1} \ B_{i−1} contains at least (1 − γ − μ − ν)^{i−1}p^{\binom{i−1}{2}}m^{i−1} different (i − 1)-tuples b = (v_{1}, …, v_{i−1}), each constituting the vertex set of a K_{i−1} in J[V_{1}, …, V_{i−1}]. For every b ∈ W_{i−1} \ B_{i−1}, we have

(i) |Γ̃_{i}(b)| ≥ (1 − γ − μ)p^{i−1}m, and (ii) d_{B_{i}}(b) < νp^{i−1}m. Therefore, every such b extends to at least (1 − γ − μ − ν)p^{i−1}m different b′ ∈ W_{i} \ B_{i} that correspond to a K_{i} ⊆ J[V_{1}, …, V_{i}]. This implies (S_{i}), and hence our induction is complete.

Assertion (S_{l}) and the choice of γ, μ, and ν in (52) give at least

(1 − γ − μ − ν)^{l}p^{\binom{l}{2}}m^{l} = (1 − σ)p^{\binom{l}{2}}m^{l}

copies of K_{l} in J.

Clearly, Lemmas 4.12 and 4.13 together imply the Counting Lemma, Lemma 2.3.

5. The d-degenerate case

In this section we describe how the proof of Theorem 1.2 extends to the proof of Theorem 1.2′. The detailed proof of Theorem 1.2′ is given in [14]. First we outline the proof of Theorem 1.2′, assuming a counterpart for the Counting Lemma, Lemma 2.3, which we state below.

Let d be an integer and H a d-degenerate graph on h vertices. Let t ≥ h ≥ 2 be fixed integers and let n be sufficiently large. Let α and ε be constants greater than 0. Suppose J is an h-partite subgraph of G with vertex classes V_{1}, …, V_{h} satisfying the following conditions: (I′) |V_{i}| = m = n/t for all i, (II′) q^{d}n ≫ (log n)^{4}, (III′) for all 1 ≤ i < j ≤ h,

|E(J_{ij})| = \begin{cases}T = pm^{2} & if \{w_{i}, w_{j}\} ∈ E(H) \\ 0 & if \{w_{i}, w_{j}\} ∉ E(H), \end{cases}

where 1 > αq = p ≫ 1/n, and

(IV′) J_{ij} (1 ≤ i < j ≤ h) is (ε, q)-regular. We now state the appropriate counting lemma for the d-degenerate case.

Lemma 2.3′ (Counting lemma, d-degenerate case). For every α, σ > 0, integer d and d-degenerate graph H on h vertices, there exists ε > 0 such that for every t ≥ h a random graph G in G(n, q) satisfies the following property with probability 1−o(1): Every subgraph J ⊆ G satisfying conditions (I′)–(IV′) contains at least

(1 − σ)p^{|E(H)|}m^{h}

copies of H.

Sketch of the proof of Theorem 1.2′. Let d be a fixed positive integer and suppose H is a d-degenerate graph of order h. Let the vertices of H be ordered w_{1}, …, w_{h} such that each w_{i} has at most d neighbours in {w_{1}, …, w_{i−1}}.

At first, we follow the proof of Theorem 1.2 and observe that, by (16), the Erdős– Stone–Simonovits theorem (see (1)) implies that F_{cluster} contains at least one copy of H if we choose t_{0}^{SRL} big enough. This yields, in the same way as in the original proof, that F contains an h-partite (ε^{Lem2.3′}, q)-regular graph J with |E(J_{ij})| = α^{Lem2.3′}qm^{2} if {w_{i}, w_{j}} ∈ E(H) and E(J_{ij}) = ∅ if {w_{i}, w_{j}} ∉ E(H). For 1 ≤ i ≤ h, we identify the vertex class V_{i} in J with the vertex w_{i} ∈ V (H).

We then apply Lemma 2.3′ with appropriate α^{Lem2.3′} and 0 < σ < 1 to deduce Theorem 1.2′.

Finally, we outline of the proof of Lemma 2.3′.

Sketch of the proof of Lemma 2.3′. We prove Lemma 2.3′ in the same way as Lemma 2.3. Observe that conditions (I) and (IV) are unchanged in Lemma 2.3′. Conditions (III) and (III′) state that J is a “blown-up” copy of the subgraph we are considering, namely, K_{l} and H, respectively. The main difference is between (II) and (II′).

The crucial part of the proof of the original counting lemma is the definition of “bad” tuples in Definition 4.8. Recall that the proof of Lemma 2.3 used the Pick-Up Lemma (Lemma 4.3). There we had to discard a small portion of the vertices of V_{i} (of high degree to some V_{j}, j < i) to obtain Ṽ_{i} ⊆ V_{i}. For 1 ≤ i ≤ |V (K_{l})|, we considered two types of “bad” (i − 1)-tuples in W_{i−1} = V_{1} × ⋯ × V_{i−1}. The first type, the ones put in B_{i−1}^{(a)}, was determined by the size of their joint neighbourhood in Ṽ_{i}. On the other hand, an (i − 1)-tuple in W_{i−1} was bad ‘of the second type’, and was put in B_{i−1}^{(b)}, if it was contained in too many “bad” i-tuples in B_{i}.

We use the property that H is d-degenerate to change the definition of B_{i}^{(a)}. In the proof of Lemma 2.3 we wanted to extend inductively each K_{i−1} in W_{i−1} that is not “bad” to the right number of copies of K_{i} in W_{i} \B_{i}. For this purpose we had to consider the joint neighbourhood of all vertices in the (i − 1)-tuple. The graph H is d-degenerate, and we fixed an ordering w_{1}, …, w_{h} of V (H) so that each w_{i} has at most d neighbours in {w_{1}, …, w_{i−1}}. This implies that it is sufficient to consider the joint neighbourhood of at most d elements of the (i − 1)-tuple to determine its “badness”, or its membership in B_{i−1}^{(a)}. For i = 1, …, h, we define the index sets I_{i} consisting of the the indices of the neighbours of w_{i} in {w_{1}, …, w_{i−1}}. Also, for a fixed (i − 1)-tuple (v_{1}, …, v_{i−1}) ∈ W_{i−1}, we consider the joint neighbourhood of ⋂ Γ(v_{j}) ∩ Ṽ_{i} =: ⋂ Γ̃(v_{j}), where the intersection is taken over j ∈ I_{i}. More precisely, we define B_{i}^{(a)} as follows:

I_{i} = {j ∈ [i − 1]: {w_{j}, w_{i}} ∈ E(H)},
B_{i−1}^{(a)}(γ, μ) = {(v_{1}, …, v_{i−1}) ∈ W_{i−1} : | ⋂_{j∈I_{i}} Γ̃_{i}(v_{j})| < (1 − γ − μ)p^{|I_{i}|}m} .

Obviously,

|I_{i}| ≤ d for 1 ≤ i ≤ h  (64)

holds. The definition of B_{i}^{(b)} remains almost unchanged; again, for some B ⊆ W_{i+1} and b = (v_{1}, …, v_{i}) ∈ W_{i}, we set d_{B}(b) = |{w ∈ Γ̃_{i+1} : (v_{1}, …, v_{i}, w) ∈ B}| and we only adjust the exponent of p:

B_{i}^{(b)} = B_{i}^{(b)}(ν) = {b ∈ W_{i}: d_{B_{i+1}}(b) ≥ νp^{|I_{i}|}m} .

Then we define the corresponding events exactly as in Definition 4.9.

The proof of Lemma 2.3 consists of two propositions (Propositions 4.10 and 4.11) and two lemmas (Lemmas 4.12 and 4.13). We now discuss the proofs of the corresponding results with the new definition for the families B_{i}^{(a)} and B_{i}^{(b)} under (I′)–(IV′) instead of (I)–(IV), and with K_{l} replaced by an arbitrary d-degenerate graph H. We define the following constants, slightly different compared to the ones in the original proof (see (52) and (53)):

γ = μ = ν = \frac{1}{3} (1 − (1 − σ)^{1/h}) ,  (65)

and, for 1 ≤ i ≤ l − 2 and |I_{i+1}| > 0,

β_{i+1} = (\frac{1}{2} (\frac{α}{e})^{∑_{j=i}^{h} |I_{j}|})^{1/|I_{i+1}|} .  (66)

The other constants are defined in the same way as described in Section 4.4 (see Figure 2, with l replaced by h).

We now discuss the proofs of the results that correspond to Propositions 4.10 and 4.11 and Lemmas 4.12 and 4.13.

Proposition 4.10. The proof is an application of the Pick-Up Lemma, Lemma 4.3, for k = i + 1. The Pick-Up Lemma does not require condition (II). It is already valid for q(n) ≫ 1/n, which is still guaranteed by (II′). It is easy to see that X_{i}^{(b)} is impossible if we set η_{i+1} = η_{i}ν/2 and if |I_{i+1}| = 0. If |I_{i+1}| > 0, then essentially the same calculation with the new β_{i+1} defined in (66) gives the proposition. We apply the Pick-Up Lemma for the space ∏_{j∈I_{i+1}} \binom{V_{j}×V_{i+1}}{T} and the projection of B_{i+1} onto ∏_{j∈I_{i+1}} V_{j} × V_{i+1}.

Proposition 4.11. The proof is a straightforward application of the k-tuple lemma, Lemma 4.7. In the original proof we apply the k-tuple lemma for k = i (1 ≤ i ≤ l − 1) and we needed condition (II) (namely, q^{l−1}n ≫ (log n)^{4}) for i = l − 1. Here, the new definition of B_{i−1}^{(a)} from above comes into play. Inequality (64) ensures that we consider at most the joint neighbourhood of d vertices. This means that we apply the k-tuple lemma for k ≤ d and thus condition (II′) (namely, q^{d}n ≫ (log n)^{4}) is sufficient.

The Turán Theorem for Random Graphs 31

Lemma 4.12. For the proof we only apply Propositions 4.10 and 4.11. In order to adjust the proof, we simply replace l by h.

Lemma 4.13. This lemma is a deterministic statement. It is not affected by the change from (II) to (II′), but the induction there is formulated in such a way that it relies on the structure (symmetries) of K_{l}. We fix this and reformulate (S_{i}) to

(S′_{i}) Let J be a subgraph of G ∉ X_{bad} such that (I′)–(IV′) apply. Then there are at least (1−γ−μ−ν)^{i}p^{∑_{j=1}^{i} |I_{j}|}m^{i} different i-tuples in W_{i}\B_{i} which induce a H[{w_{1}, …, w_{i}}]

in J[V_{1}, …, V_{i}].

Thus, the induction works exactly the same way and (S′_{h}) implies the result, by our choice of the constants in (65) (there we again replace l with h and \binom{l}{2} with |E(H)|).

References

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

[2] , Random graphs, second ed., Cambridge University Press, Cambridge, 2001.

[3] P. Frankl and V. Rödl, Large triangle-free subgraphs in graphs without K_{4}, Graphs Combin. 2 (1986), no. 2, 135–144.

[4] Z. Füredi, Random Ramsey graphs for the four-cycle, Discrete Math. 126 (1994), no. 1-3, 407–410.

[5] P. E. Haxell, Y. Kohayakawa, and T. Łuczak, Turán’s extremal problem in random graphs: forbidding even cycles, J. Combin. Theory Ser. B 64 (1995), no. 2, 273–287.

[6] , Turán’s extremal problem in random graphs: forbidding odd cycles, Combinatorica 16 (1996), no. 1, 107–122.

[7] S. Janson, T. Łuczak, and A. Ruciński, Random graphs, Wiley-Interscience, New York, 2000.

[8] Y. Kohayakawa, Szemerédi’s regularity lemma for sparse graphs, Foundations of computational mathematics (Rio de Janeiro, 1997) (F. Cucker and M. Shub, eds.), Springer, Berlin, January 1997, pp. 216–230.

[9] Y. Kohayakawa, B. Kreuter, and A. Steger, An extremal problem for random graphs and the number of graphs with large even-girth, Combinatorica 18 (1998), no. 1, 101–120.

[10] Y. Kohayakawa, T. Łuczak, and V. Rödl, On K^{4}-free subgraphs of random graphs, Combinatorica 17 (1997), no. 2, 173–213.

[11] Y. Kohayakawa and V. Rödl, Regular pairs in sparse random graphs I, submitted, 2001.

[12] , Szemerédi’s regularity lemma and quasi-randomness, Recent Advances in Algorithmic Combinatorics (B. Reed and C. Linhares-Sales, eds.), CMS Books in Mathematics, vol. 10, Springer, Berlin, 2002, to appear.

[13] D. R. Lick and A. T. White, k-degenerate graphs, Canad. J. Math. 22 (1970), 1082–1096.

[14] M. Schacht, The Turán theorem for random graphs, Master’s thesis, Department of Mathematics and Computer Science, Emory University, expected 2002.

[15] J. M. S. Simões-Pereira, A survey of k-degenerate graphs, Graph Theory Newslett. 5 (1975/76), no. 6, 1–7.

[16] T. Szabó and V. H. Vu, Turán’s theorem in sparse random graphs, Random Structures Algorithms, to appear.

[17] E. Szemerédi, Regular partitions of graphs, Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), CNRS, Paris, 1978, pp. 399–401.

32 Y. Kohayakawa, V. Rödl, and M. Schacht

[18] P. Turán, Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok 48 (1941), 436–