A Turán theorem for random graphs

by Mathias Schacht Master of Science

Department of Mathematics and Computer Science

Vojtěch Rödl Advisor

Yoshiharu Kohayakawa Advisor

Dwight Duffus Committee Member

Andrzej Ruciński Committee Member

Accepted:

Dean of the Graduate School

Date

A Turán theorem for random graphs

by

Mathias Schacht

Advisors : Vojtěch Rödl, Ph.D.

Yoshiharu Kohayakawa, Ph.D.

Abstract of

a thesis submitted to the Faculty of the Graduate School

of Emory University in partial fulfillment

of the requirements of the degree of Master of Science

Department of Mathematics and Computer Science

Abstract

Turán’s theorem is one of the cornerstones of extremal graph theory today. The aim of this thesis is to prove a Turán type theorem for sparse random graphs.

For 0 < γ ≤ 1 and graphs G and H, write G →_{γ} H if any γ-proportion of the edges of G contains at least one copy of H in G. In this thesis, we prove that for every d-degenerate graph H and every fixed real γ > 1−1/(χ(H)−1) asymptotically almost surely a graph G in the binomial random graph model G(n, q) with q = q(n) ≫ ((log n)^{4}/n)^{1/d} satisfies G →_{γ} H, where as usual χ(H) denotes the chromatic number of H.

As a corollary we immediately derive that for every l ≥ 2 and every fixed real γ > 1 − 1/(l − 1) asymptotically almost surely a graph G in G(n, q) with q = q(n) ≫ ((log n)^{4}/n)^{1/(l−1)} satisfies G →_{γ} K_{l}, where K_{l} is the complete graph on l vertices.

by

Mathias Schacht

Advisors : Vojtěch Rödl, Ph.D.

Yoshiharu Kohayakawa, Ph.D.

A thesis submitted to the Faculty of the Graduate School

of Emory University in partial fulfillment

of the requirements of the degree of Master of Science

Department of Mathematics and Computer Science

Acknowledgments

I would like to thank both of my advisors Vojtěch Rödl and Yoshiharu Kohayakawa for their time and encouragement. I would also like to thank to Dwight Duffus and Andrzej Ruciński for serving on my thesis committee.

Moreover, I would like to express my appreciation to the people who established and continue the exchange program of the Technical University of Berlin, Germany and Emory University. In particular, I would like to thank Vladimir Oliker and Ronald J. Gould from Emory University and Udo Simon from the Technical University of Berlin.

Contents

1 Introduction 1

2 Preliminary results 6 2.1 Preliminary definitions . . . . . . . . . . . . . . . . . . . . . . 6 2.2 The regularity lemma for sparse graphs . . . . . . . . . . . . . 7 2.3 The counting lemma . . . . . . . . . . . . . . . . . . . . . . . 8

3 The main result 10 3.1 Properties of almost all graphs . . . . . . . . . . . . . . . . . . 10 3.2 A deterministic subgraph lemma . . . . . . . . . . . . . . . . . 12 3.3 Proof of the main result . . . . . . . . . . . . . . . . . . . . . 15

4 The counting lemma 20 4.1 The pick-up lemma . . . . . . . . . . . . . . . . . . . . . . . . 20 4.2 The k-tuple lemma for subgraphs of random graphs . . . . . . 29 4.3 Illustration of the proof of the counting lemma for H = K_{4} − e 30 4.4 Proof of the counting lemma . . . . . . . . . . . . . . . . . . . 33

4.4.1 Concepts and constants . . . . . . . . . . . . . . . . . 33 4.4.2 Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.4.3 Main proof . . . . . . . . . . . . . . . . . . . . . . . . 46

List of Figures

4.1 “bad” tuples . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2 Flowchart of the constants . . . . . . . . . . . . . . . . . . . . 38

Chapter 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), the Turán number of 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. In the special case where H = K_{l} is the complete graph on l vertices this question was answered precisely by Turán.

Theorem 1 (Turán [25]). Given integers n ≥ l > 1. Let r = n mod _{l−1}, then

ex(n, K_{l}) = \frac{1}{2} (1 − \frac{1}{l − 1}) (n^{2} − r^{2}) + \binom{r}{2}.

An asymptotic solution to the general problem (for arbitrary graphs H) is given by the following celebrated theorem.

Theorem 2 (Erdős–Stone–Simonovits [5, 6]). For every graph H with chromatic number χ(H)

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

where o(1) is a function approaching zero as n goes to infinity.

Furthermore, as proved independently by Erdős [3, 4] and Simonovits [22], every H-free graph G = G^{n} that has as many edges as in (1.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 Hfree 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 [2, 12].) As is usual in the theory of random graphs, we say that a property P holds asymptotically almost surely (abbreviated a.a.s.) if P holds with probability tending to 1 as n → ∞.

Here we wish to investigate the random variable ex(G(n, q), H). Since Theorem 2 can be viewed as a result for random graphs G(n, q) with q = 1, naturally, the question arises for which q = q(n) the formula (1.1) remains true with K_{n} replaced by G(n, q) and \binom{n}{2} = |E(K_{n})| by q\binom{n}{2} (the expected number of edges in the random graph G(n, q)). We are interested in the probabilities q = q(n) for which a.a.s.

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

holds. It follows from [12, Proposition 8.6] that if equality (1.2) holds a.a.s. for p_{1}, then it does so for each p_{2} ≥ p_{1}. Thus, we are interested in the smallest probability q = q(n) such that (1.2) holds.

If q = q(n) is such that the expected number of copies of H in G ∈ G(n, q) is much smaller than the expected number of edges of G, then it is not hard to show that (1.2) fails (see [12, Proposition 8.9]). Conjecture 3, stated below, demonstrates the belief that this is the only obstacle. The observation that containing H implies containing every subgraph H′ of H, leads to the following definition.

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

m_{2}(H) = max \{\frac{|E(H′)| − 1}{|V (H′)| − 2} : H′ ⊂ H, |V (H′)| ≥ 3\} .

A general conjecture concerning ex(G(n, q), H), first stated in [15], is as follows.

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

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

There are a few results in support of Conjecture 3. A simple application of Szemerédi’s regularity lemma for sparse graphs (see Theorem 8 below), gives Conjecture 3 for H a forest. The cases in which H = K_{3} and H = C_{4} are essentially proved in Frankl and Rödl [7] and Füredi [8], 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 [15]. Recently Schickinger proved in his Ph.D. thesis [20] a somewhat stronger conjecture for H = K_{5} (and H = K_{4} as well, see also Gerke et al. [9]), which implies Conjecture 3 for this case. The case in which H is a general cycle was settled by Haxell, Kohayakawa, and Łuczak [10, 11] (see also Kohayakawa, Kreuter, and Steger [14]).

Our main result relates to Conjecture 3 in the following way: we deal with the case in which H is arbitrary and q = q(n) ≫ ((log n)^{4}/n)^{1/d}, where d = d(H) is the “degeneracy number” of H (defined below) and q(n) ≫ ((log n)^{4}/n)^{1/d} means lim_{n→∞}((log n)^{4}/n)^{1/d}/q(n) = 0. Definition 4 (d-degenerate). A graph H of order h is called d-degenerate if there exists an ordering of the vertices V (H) = {w_{1}, …, w_{h}} such that each w_{i} (1 ≤ i ≤ h) has at most d neighbours in {w_{1}, …, w_{i−1}}. Moreover, we denote the degeneracy number of H by the minimal integer d = d(H) for which H is d-degenerate. For more details concerning d-degenerate graphs see [19, 21]).

The following theorem is the main result of this thesis.

Theorem 5. Let d be a positive integer, H a d-degenerate graph of order h, and q = q(n) ≫ ((log n)^{4}/n)^{1/d}. Then for every 1/(χ(H) − 1) > δ > 0 a graph G in G(n, q) satisfies a.a.s. the following property: 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.

In this thesis we give a proof of Theorem 5. Since K_{l}, the complete graph on l vertices, is clearly (l−1)-degenerate and l-chromatic, the following result is an immediate consequence of Theorem 5.

Corollary 6. Let l ≥ 2, and q = q(n) ≫ ((log n)^{4}/n)^{1/(l−1)}. Then for every 1/(l − 1) > δ > 0 a graph G in G(n, q) satisfies a.a.s. the following property: 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} 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}.

The main result discussed in this thesis (Theorem 5) was already announced by the author and his advisors in [18]. There a simpler proof for the case H = K_{l} for l ≥ 2 was given. In this thesis we give a proof for arbitrary graphs H, which is based on the ideas of [18].

Very recently Szabó and Vu proved in [23], independently from us, Corollary 6 under slightly weaker assumptions. Their proof is shorter than the proof of Theorem 5 presented here and does not require the regularity lemma. On the other hand, their approach does not seem to extend to arbitrary graphs H, whereas Theorem 5 gives nontrivial results for arbitrary H depending on the “degeneracy number” of the graph H.

This thesis is organized as follows. In Chapter 2 we describe a sparse version of Szemerédi’s regularity lemma (Theorem 8) and we state the counting lemma (Lemma 10), both of which are crucial in our proof of Theorem 5. We prove Theorem 5 in Chapter 3. Chapter 4 is entirely devoted to the proof of Lemma 10. The proof of Lemma 10 relies on the ‘Pick-Up Lemma’ (Lemma 18) and on the ‘k-tuple Lemma’ (Lemma 22). We give these preliminary results in Section 4.1–4.2. In Section 4.3 we outline the proof of Lemma 10 in the case H = K_{4} − e, the complete graph on four vertices minus an edge. Finally, the proof of Lemma 10 is given in Section 4.4.

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

Chapter 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)|, i.e. for the complete graph K_{l} we have

e_{K_{l}} = |U||W | − \binom{|U ∩ W | + 1}{2}.

Suppose ξ > 0, C > 1, and 0 < q ≤ 1. Definition 7 ((ξ, C)-bounded). For ξ > 0 and C > 1 we say that G = (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_{G}(U, W) ≤ Cq (|U||W | − \binom{|U ∩ W | + 1}{2}) .

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

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

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

We refer to d_{G,q}(U, W) as the q-density of the pair (U, W) in G. When there is no danger of confusion, we drop G 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 (ε, G, q)-regular, or simply (ε, q)-regular, if for all U′ ⊂ U, W′ ⊂ W with |U′| ≥ ε|U| and |W′| ≥ ε|W | we have

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

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 (G) 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 (ε, G, 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 8. 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 G that is (ξ, C)-bounded with respect to density 0 < q ≤ 1 admits an (ε, G, 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 8. For applications of this variant of the regularity lemma and its proof, see [13, 17].

2.3 The counting lemma

Let H be a fixed d-degenerate graph on h vertices and let the vertices of H be ordered V (H) = {w_{1}, …, w_{h}} such that each w_{i} has at most d neighbours in {w_{1}, …, w_{i−1}}. Let t ≥ h be a fixed integer 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 h-partite subgraph of G with vertex classes V_{1}, …, V_{h}. For all 1 ≤ i < j ≤ h we denote by J_{ij} the bipartite graph induced by V_{i} and V_{j}. Consider the following assertions for J and q.

(I) |V_{i}| = m = n/t

(II) q^{d}n ≫ (log n)^{4}

(III) for all 1 ≤ i < j ≤ h,

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

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

(IV) J_{ij} is (ε, q)-regular.

Remark 9. Strictly speaking, in (I) we should have, say, ⌊n/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 the fixed graph H in such a subgraph J satisfying conditions (I)–(IV).

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

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

copies of H.

We will prove Lemma 10 in Chapter 4.

Chapter 3

The main result

In this section we will prove the main result of this thesis, Theorem 5. This section is organised 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 5.

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 11. For every real ϱ > 0, if G is a random graph in G(n, q), then

(1 − ϱ) q\binom{n}{2} ≤ e(G) ≤ (1 + ϱ) q\binom{n}{2}

holds with probability 1 − o(1).

The next property refers to Definition 7 and will enable us to apply Theorem 8.

Lemma 12. 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. For the next lemma, recall that all logarithms are to base e, see the Remark 9 in Section 2.3.

Lemma 13. Let X be a binomially distributed random variable 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.

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

Proof of Lemma 12. 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 | + 1}{2}) .

Observe that 𝔼[e(U, W)] ≫ n since q ≫ 1/n. Set τ = log C − 1 + 1/C. Then Lemma 13 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 a (3ε, q)-regular subgraph with exactly αqm^{2} edges.

Lemma 14. 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} and m_{1}, 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}

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′|}.  (3.1)

In order to check the (3ε, H′, q)-regularity of (U, W), it is enough to verify the inequality corresponding to (2.2) 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}.  (3.2)

Since H is (ε, H, q)-regular

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

On the other hand, d_{H′,q}(X, Y) ≤ d_{H,q}(X, Y) for arbitrary X ⊆ U and Y ⊆ W, which combined with (3.2) and (3.3) 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 15. 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 [12] (Theorem 2.10).

We continue with the proof of Lemma 14. 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′)| ≤ ε  (3.4)

implies that

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

Indeed, straightforward calculation using the (ε, q)-regularity of H and (3.4) 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 (3.4) is unlikely to fail, because of the random choice of D. We set

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

Then the two-sided estimate in Lemma 15 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)}) .  (3.7)

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 (3.6), 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 (3.4) and consequently (3.5) fails with small probability given in (3.7).

We now sum over all possible choices for U′ and W′ and use |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 5 is based on Lemma 10, which we prove later in Chapter 4. The main idea is to “find” a subgraph J satisfying (I)–(IV) of the Counting Lemma, in the arbitrary subgraph F with

e(F) ≥ (1 − \frac{1}{χ(H) − 1} + δ) q\binom{n}{2}.

Proof of Theorem 5. Let H be a fixed d-degenerate graph on h vertices and let the vertices of H be ordered V (H) = {w_{1}, …, w_{h}} such that each w_{i} has at most d neighbours in {w_{1}, …, w_{i−1}}. Let 1/(χ(H) − 1) > δ > 0 be fixed and suppose q = q(n) ≫ ((log n)^{4}/n)^{1/d}. First we define some constants that will be used in the proof.

We start by setting

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

(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 10, in order to determine the value of ε. Set α^{CL} = α and σ^{CL} = σ, then Lemma 10 yields ε^{CL}. We set

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

and

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

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

ξ = ξ^{SRL}.

Moreover, Theorem 8 yields

T_{0}^{SRL} ≥ t = t^{SRL} ≥ t_{0}^{SRL} = max \{h, \frac{40}{δ}\} .  (3.12)

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

Fact 11, Lemma 12, and Lemma 10 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 10.

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

To achieve this, we first regularise F by applying Theorem 8 with ε^{SRL} = ε, C^{SRL} = C and t_{0}^{SRL} = max{h, 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 Theorem 2 to guarantee the existence of a copy of H in 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, (3.8), (3.10), (3.11), (3.12), 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}{χ(H) − 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}{χ(H) − 1} + \frac{δ}{2}) (1 − \frac{1}{n}) (1 + \frac{δ}{4})^{−1} \frac{t^{2}}{2} ,

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

e(F_{cluster}) > (1 − \frac{1}{χ(H) − 1} + \frac{δ}{2}) (1 − \frac{δ}{4}) \frac{t^{2}}{2}
≥ (1 − \frac{1}{χ(H) − 1} + \frac{δ}{8}) \binom{t}{2}

The last inequality implies, by Theorem 2, that F_{cluster} contains H as a subgraph. Let {i_{1}, …, i_{h}} be the vertex set of this H in F_{cluster}. Then we set J_{0} = F [V_{i_{1}}, …, V_{i_{h}}] ⊆ F. Now, for every edge {w_{j}, w_{j′}} ∈ E(H) the pair (V_{i_{j}}, V_{i_{j′}}) satisfies the conditions of Lemma 14 with ε^{Lem14} = ε, α^{Lem14} = α, and C^{Lem14} = C. 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} for every {w_{j}, w_{j′}} ∈ E(H). Observe ε ≤ ε^{CL}/3 and J satisfies conditions (I)–(IV) of the Counting Lemma, Lemma 10, with the constants chosen above (α^{CL} = α, σ^{CL} = σ, and ε^{CL} ≥ 3ε), and thus there are at least

(1 − σ)p^{e(H)}m^{h} = \frac{(1 − σ)α^{e(H)}}{t^{h}} q^{e(H)}n^{h} ≥ \frac{(1 − σ)α^{e(H)}}{(T_{0}^{SRL})^{h}} q^{e(H)}n^{h}

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

Chapter 4

The counting lemma

Our aim in this section is to prove Lemma 10. In order to do this, we will need two lemmas (Lemma 18 and 22). We introduce these in the first two sections. Then, in Section 4.3, we will illustrate the proof of the Counting lemma on the particular case H = K_{4} − e. Finally, we give the proof of Lemma 10 in Section 4.4.

4.1 The pick-up lemma

Before we state the ‘Pick-Up Lemma’, Lemma 18, let us state a simple onesided estimate for the hypergeometric distribution, which will be useful in the proof of Lemma 18.

Lemma 16 (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} .  (4.1)

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

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 1 ≤ i < k and R_{i} ∈ \binom{V_{i}×V_{k}}{T} the degree with respect to R_{i} of a vertex v_{k} in V_{k} is

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

Definition 17 (Π(ζ, μ, K, B)). For ζ, μ, K with 1 > ζ, μ > 0 and K > 0 and B ⊆ V_{1} × ⋯ × V_{k}, we say that property Π(ζ, μ, K, B) 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} and (v_{j}, v_{k}) ∈ R_{j}, ∀ 1 ≤ j ≤ k − 1}

satisfy the inequalities

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

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, B) fails for a fixed B in the uniform probability space Ω.

Lemma 18 (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}, B ⊆ V_{1} × ⋯ × V_{k} and

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

then

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

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

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

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}  (4.9)

holds for m sufficiently large.

Using the definition of d_{R_{i}} in (4.2) 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 18 we define the following “bad” events in Ω. Definition 19 (A_{i}, B). For each i = 0, …, k − 1 and K, μ > 0, ζ > 0, and B ⊆ V_{1} × ⋯ × V_{k} 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.  (4.10)

We restate Lemma 18 by using the notation introduced in Definition 19. Lemma 18′ (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}, B ⊆ V_{1} × ⋯ × V_{k} and

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

then

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

We need some more preparation before we prove Lemma 18′. Suppose β, ζ, μ are given by Lemma 18′ and θ, K are fixed by (4.7) and (4.8). 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)} and (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}.  (4.13)

(Equality may fail in (4.13) 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}}.  (4.14)

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}.  (4.15)

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

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

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

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

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

Assuming Claims 20 and 21, we may easily prove Lemma 18′.

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

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

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

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

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})  (4.18)

for each i = 1, …, k − 1. It follows by applying (4.17) and (4.18) 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 20 and 21, and (4.10), (4.16) and (4.7) 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 20 and then Claim 21.

Proof of Claim 20. 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}.  (4.19)

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

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

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)} )  (4.21)

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 (4.9) 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 21. Recall β, ζ and μ are given by Lemma 18′ and θ, K and ζ_{i} are fixed by (4.7), (4.8) and (4.14). In order to prove Claim 21 we fix i (1 ≤ i ≤ k − 1) and we assume ¬A_{i−1} and ¬B_{i−1} occur. This means by Definition 19 and (4.15) that

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

We have to show that

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

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}} .  (4.25)

The definition of θ in (4.7) 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}  (4.26)

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 (4.22) and (4.23):

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)}|}  (4.27)

≤ \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}. (4.28)

Inequality (4.28) implies

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

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 (4.27) 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}. (4.30)

On the other hand, if we set F̄ = V_{i} × V_{k}^{(i−1)} \ F then the definition of F and (4.29) 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}.  (4.31)

Next we prove that

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

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

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

We now prove inequality (4.32). Without loss of generality we assume equality holds in (4.30). Then the hypergeometric tail lemma, Lemma 16, 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}  (4.34)

≤ 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 (4.26)). The definitions of ζ_{i−1} and L_{i} in (4.14) and (4.25) 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 (4.34), gives (4.32).

4.2 The k-tuple lemma for subgraphs of ran-

dom 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 22 (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}  (4.35)

also applies. Proof. The proof of Lemma 22 is given in [16].

4.3 Illustration of the proof of the counting

lemma for H = K_{4} − e

The proof of the Lemma 10 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 where H is the 2-degenerate graph isomorphic to K_{4} − e, before we give the proof for a general H in Section 4.4.

We fix an order of the vertices {w_{1}, w_{2}, w_{3}, w_{4}} of K_{4} − e as pictured in Figure 4.1(a). 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} ({w_{i}, w_{j}} ∈ E(H)), where p = αq. We will describe a situation in which we will be able to assert that J contains the “right” number of H’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 H = K_{4} − e’s, this means ∼ p^{5}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 h − 1 = 3 stages. First we choose the edges from V_{4} to V_{1} ∪ V_{3} (since {w_{4}, w_{2}} is not an edge in H). 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}.

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

Figure 4.1: “bad” tuples

The key idea of the proof is to consider “bad” tuples, which we create in every stage. After we chose the edges from V_{4} to V_{1} ∪ V_{3}, we define “bad” 3tuples in V_{1}×V_{2}×V_{3}: a 3-tuple (v_{1}, v_{2}, v_{3}) is “bad” if the joint neighbourhood of v_{1} and v_{3} in V_{4} is much smaller than expected. Then, with the right choice of constants, Proposition 26 for k = 2 and J = J[V_{4}, V_{1} ∪ V_{3}] will ensure that there are not too many “bad” 3-tuples. (Proposition 26 is a corollary of the the k-tuple lemma, Lemma 22.)

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 25): 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 4.1(b)), 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 4.1(c)). This will be ensured by the the k-tuple lemma (to be more precise, Proposition 26), 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 23 below). We define B_{i} as the union of the sets B_{i}^{(a)} and B_{i}^{(b)}, defined as follows. Let I_{i+1} = {j ∈ [i]: {w_{i+1}, w_{j}} ∈ E(H)} We put in B_{i}^{(a)} the i-tuples (v_{1}, …, v_{i}) that are “bad” because the joint neighbourhood of {v_{j}: j ∈ I_{i+1}} in Ṽ_{i+1} 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 = h − 1, …, 1) by reverse induction, starting with B_{h−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 H = K_{4} − e’s. We will use the following deterministic argument, which will later be formalised in Lemma 29. 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” 2-tuple. In other words, this means that v_{1} extends to ∼ pm copies of H_{2} = H[{w_{1}, w_{2}}] in (V_{1} × V_{2}) \ B_{2}. This implies that each such H_{2} has the right number of joint neighbours in Ṽ_{3} (i.e., ∼ p^{2}m), and consequently extends to the right number of H_{3} = H[{w_{1}, w_{2}, w_{3}}]’s in (V_{1} × V_{2} × V_{3}) \ B_{3}. Repeating the last argument, each of these H_{3}’s extends into ∼ p^{2}m (since w_{4} is only adjacent to w_{1} and w_{3}) different copies of H = K_{4} − e. Since we have ensured that most of the m vertices in V_{1} are not “bad”, we have ∼ m · pm · p^{2}m · p^{2}m = p^{e(H)}m^{4} copies of H.

4.4 Proof of the counting lemma

In this section we will prove Lemma 10. In Section 4.4.1, 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 Section 4.4.2. 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 Section 4.4.3.

4.4.1 Concepts and constants

Let H be a fixed d-degenerate graph on h vertices and let the vertices of H be ordered V (H) = {w_{1}, …, w_{h}} such that each w_{i} hast at most d neighbours in {w_{1}, …, w_{i−1}}. For every 1 ≤ i ≤ h we set I_{i} to the set of the indices of the neighbours of w_{i} in {w_{1}, …, w_{i−1}}

I_{i} = Γ_{H}(w_{i}) ∩ {w_{1}, …, w_{i−1}}.

Let t ≥ h be a fixed integer and n a sufficiently large integer. Let α and ε be constants greater than 0. Let G be in G(n, q) with q = q(n), and suppose J is an h-partite subgraph of G with vertex classes V_{1}, …, V_{h}. For all 1 ≤ i < j ≤ h we denote by J_{ij} the bipartite graph induced by V_{i} and V_{j}. Consider the following assertions for J and q.

(I) |V_{i}| = m = n/t

(II) q^{d}n ≫ (log n)^{4}

(III) for all 1 ≤ i < j ≤ h,

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

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

(IV) J_{ij} is (ε, q)-regular.

Let σ > 0 be given. We define the constants

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

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

β_{i+1} = \begin{cases}(\frac{1}{2} (\frac{α}{e})∑_{j=i+1}^{h} |I_{j}|)1/|I_{i+1}| & I_{i+1} ≠ ∅ \\ 0 & I_{i+1} = ∅ \end{cases} .  (4.37)

In order to prove Lemma 10 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, …, h 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 ≤ h − 1). We define these sets recursively from B_{h−1} to B_{1}. As mentioned above in the discussion of the H = K_{4} − e case, there are two reasons that make a given i-tuple (v_{1}, …, v_{i}) in W_{i} “bad”. First of all, its joint neighbourhood of {v_{j}: j ∈ I_{i+1}} in V_{i+1} might be too small (see the definition of B_{i}^{(a)} in Definition 23) 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 23). 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_{i+1}| + 1 if |I_{i+1}| > 0 (1 ≤ i ≤ h − 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

with probability bigger than

1 − (β_{i+1}^{PU})^{|I_{i+1}|T} .

For 2 ≤ i + 1 ≤ h − 1 such that |I_{i+1}| = 0 we simply set Ṽ_{i+1} = V_{i+1} and, therefore, trivially |Ṽ_{i+1}| ≥ (1 − μ)m holds.

We need a few more definitions before we define B_{i}, B_{i}^{(a)} and B_{i}^{(b)} (recursively for i = h − 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}), ∀ j ∈ I_{i+1}}.

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) = |{v ∈ Γ̃_{i+1}(b): (v_{1}, …, v_{i}, v) ∈ 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 = h, for the sake of convenience we consider the neighbourhood of elements in W_{h−1} in Ṽ_{h}, instead of in V_{h}. Definition 23 (B_{l−1}, B_{i}^{(a)}, B_{i}^{(b)}, B_{i}). Let γ, μ, ν be given by (4.36). We define recursively the following sets of “bad” tuples for i = h − 1, …, 1:

\begin{aligned}B_{h−1} & = & B_{h−1}(γ, μ) & = & \{b ∈ W_{h−1} : |Γ̃_{h}(b)| < (1 − γ − μ)p^{|I_{h}|}m\} , \\ B_{i}^{(a)} & = & B_{i}^{(a)}(γ, μ) & = & \{b ∈ W_{i}: |Γ̃_{i+1}(b)| < (1 − γ − μ)p^{|I_{i+1}|}m\} , \\ B_{i}^{(b)} & = & B_{i}^{(b)}(ν) & = & \{b ∈ W_{i}: d_{B_{i+1}}(b) ≥ νp^{|I_{i+1}|}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_{h−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 24. Let γ, μ, ν be given by (4.36) and let η_{i} > 0 (i = h − 1, …, 1) be fixed. We define the events

X_{h−1}(γ, μ, η_{h−1}): ∃ J ⊆ G s.t. |B_{h−1}| > (η_{h−1}/2)m^{h−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_{h−1}^{(a)} = X_{h−1} = X_{h−1}(γ, μ, η_{h−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 (4.36) and β_{i} for 2 ≤ i ≤ h − 1 in (4.37). The (yet unspecified) parameters η_{i} and ε will be determined by Propositions 25 and 26. First we set η_{1} = ν. Then Proposition 25 (PU_{i+1}) inductively describes η_{i+1} = η_{i+1}(β_{i+1}, γ, μ, ν, η_{i}) for i = 1, …, h − 2 such that ℙ(X_{i}^{(b)}) = o(1). Finally, for i = 1, …, h − 1, Proposition 26 (TL_{i}) implies the choice for ε_{i} = ε_{i}(α, γ, μ, η_{i}) such that ℙ(X_{i}^{(a)}) = o(1). We set

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

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

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

4.4.2 Tools

We need some auxiliary results before we prove Lemma 10. For this purpose we state variants of the Pick-Up Lemma, Lemma 18, and of the k-tuple

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

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

ε = min ε_{i}

Figure 4.2: Flowchart of the constants

lemma, Lemma 22, 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 18 for k = |I_{i+1}| + 1 (1 ≤ i ≤ h − 2).

Proposition 25 (PU_{i+1}). Fix 1 ≤ i ≤ h − 2. Let α, σ > 0 be arbitrary, let γ, μ, ν and β_{i+1} be given by (4.36) and (4.37), and let η_{i} be defined as stated in Section 4.4.1 (see Figure 4.2). Then there exists η_{i+1} = η_{i+1}(β_{i+1}, γ, μ, ν, η_{i}) > 0 such that for every t ≥ h 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},  (4.38)

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

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

is less than

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

which means

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

Furthermore,

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

holds.

We restate Proposition 25, by using the events X_{i}^{(b)} from Definition 24. Observe that inequalities (4.38) and (4.39) correspond to the event X_{i}^{(b)}, so that ℙ(X_{i}^{(b)}) = o(1) is equivalent to the first part of Proposition 25′. Proposition 25′ (PU_{i+1}). Fix 1 ≤ i ≤ h − 2. Let α, σ > 0 be arbitrary, let γ, μ, ν and β_{i+1} be given by (4.36) and (4.37), and let η_{i} be defined as stated in Section 4.4.1 (see Figure 4.2). Then there exists η_{i+1} = η_{i+1}(β_{i+1}, γ, μ, ν, η_{i}) > 0 such that for every t ≥ h

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

and

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

Proof. If |I_{i+1}| = 0 we simply set η_{i+1} = η_{i}ν/2 and Ṽ_{i+1} = V_{i+1}. Suppose (4.38) holds and (4.39) fails. Then we derive

|B_{i+1}| > \frac{η_{i}}{2} m^{i} · νp^{|I_{i+1}|}m = η_{i+1}p^{0}m^{i+1},

which contradicts (4.38).

Therefore, we assume |I_{i+1}| > 0. We apply Lemma 18 for k = |I_{i+1}| + 1 and with the following choice of β^{PU}, ζ^{PU}, μ^{PU}:

β^{PU} = β_{i+1},
ζ^{PU} = \frac{η_{i}ν}{2} ,
μ^{PU} = μ.

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

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

We assume inequality (4.38) 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}.  (4.40)

On the other hand, if we assume that (4.39) 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_{i+1}|}m = ζ^{PU}p^{|I_{i+1}|}m^{i+1}.  (4.41)

In particular at least ζ^{PU}p^{|I_{i+1}|}m^{|I_{i+1}|+1} different (|I_{i+1}| + 1)-tuples of B′_{i+1} were “picked-up”, where

B′_{i+1} = B_{i+1}|_{(∏_{j∈I_{i+1}} V_{j})×V_{i+1}}

is the restriction of B_{i+1} on (∏_{j∈I_{i+1}} V_{j})×V_{i+1}. The Pick-Up Lemma bounds the number of these configurations in

∏_{j∈I_{i+1}} \binom{V_{j} × V_{i+1}}{T}

by

(β^{PU})^{|I_{i+1}|T} · \binom{m^{2}}{T}^{|I_{i}+1|} = (β_{i+1})^{|I_{i+1}|T} \binom{m^{2}}{T}^{|I_{i}+1|}.  (4.42)

We now estimate the number of all possible graphs J satisfying (I)–(IV) for which (4.40) holds but the number of members in B_{i+1} that have been “picked-up” exceeds (4.41). There are less than \binom{n}{m}^{h} different ways to fix the h vertex classes of J. Furthermore, observe that B_{i+1} and, therefore, B′_{i+1} are determined by all the edges in J_{jj′} (i + 1 < j′ ≤ h, 1 ≤ j < j′ ≤ h, which gives L = ∑_{l=i+2}^{h} |I_{l}| different pairs (j, j′) with e(J_{jj′}) ≠ 0. Thus we have at most \binom{m^{2}}{T}^{L} possibilities to determine B_{i+1} (i.e., B′_{i+1}). This, combined with (4.42), (III), and (4.37) yields that

ℙ (X_{i}^{(b)}) ≤ \binom{n}{m}^{h}\binom{m^{2}}{T}^{L} · (β_{i+1})^{|I_{i+1}|T} \binom{m^{2}}{T}^{|I_{i+1}|} · q^{(L+|I_{i+1}|)T}

≤ 2^{nh} (\frac{em^{2}q}{T} )^{(L+|I_{i+1}|)T} (β_{i+1})^{|I_{i+1}|T}

≤ 2^{nh} ((\frac{e}{α})^{∑_{j=i+1}^{h} |I_{j}|} (β_{i+1})^{|I_{i+1}|})^{T}

≤ 2^{nh−T} .

Since h 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 25′ also follows from the proof above.

The following is an easy consequence of Lemma 22 for k = |I_{i+1}| (1 ≤ i ≤ h − 1).

Proposition 26 (TL_{i}). Fix 1 ≤ i ≤ h − 1. Let α, σ > 0 be arbitrary, let γ, μ be given by (4.36), and let η_{i} be defined as stated in Section 4.4.1 (see Figure 4.2). Then there exists ε_{i} = ε_{i}(α, γ, μ, η_{i}) > 0 such that for every t ≥ h 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_{i+1}|}m

is less than

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

which means that

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

We can reformulate Proposition 26 in a shorter way by using the event X_{i}^{(a)} (see Definition 24). Proposition 26′ (TL_{i}). Fix 1 ≤ i ≤ h − 1. Let α, σ > 0 be arbitrary, let γ, μ be given by (4.36) and let η_{i} be defined as stated in Section 4.4.1 (see Figure 4.2). Then there exists ε_{i} = ε_{i}(α, γ, μ, η_{i}) > 0 such that for every t ≥ h and ε ≤ ε_{i}

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

Proof. The proposition is trivial if |I_{i+1}| = 0. Therefore, without loss of generality assume |I_{i+1}| > 0.

We apply the k-tuple lemma, Lemma 22, with k = |I_{i+1}|, α^{TL} = α/3, γ^{TL} = γ and

η^{TL} = \frac{η_{i}}{(2i^{i})}.  (4.44)

The k-tuple lemma gives an ε^{TL} and without loss of generality we may assume

ε^{TL} ≤ \frac{2}{7}.  (4.45)

We set

ε_{i} = min \{(ε^{TL})^{3} , 1 − μ, \frac{α}{2}\} .

Let ε ≤ ε_{i} and J be a subgraph of G ∈ G(n, q) satisfying (I)–(IV). Set U = Ṽ_{i+1} and W = ⋃_{j∈I_{i+1}}^{i} V_{j}. By (IV), the graph J_{jj′} (1 ≤ j < j′ ≤ i) is (ε, q)-regular. Due to Lemma 12 without loss of generality we may assume G is (ξ, 3/2)-bounded for some ξ < ε Below, we verify that condition (i) and (ii) of Lemma 22 hold for J[U, W] with respect to G.

Claim 27.

(i) e(J[U, W]) ≥ α^{TL}e(G[U, W]),

(ii) J[U, W] is (ε^{TL}, q)-regular, Proof of Claim 27. First we show (i). Since G is (ξ, 3/2)-bounded

e(G[U, W]) ≤ \frac{3}{2}q(1 − μ)|I_{i+1}|m^{2}.

On the other hand, using the (ε, q)-regularity of J_{j,i+1} for every j ∈ I_{i+1} we derive

e(J[U, W]) ≥ (α − ε)q(1 − μ)|I_{i+1}|m^{2}

and, therefore, applying the choice of ε and α^{TL} gives

\frac{e(J[U, W])}{e(G[U, W])} ≥ \frac{2(α − ε)}{3} ≥ \frac{α}{3} ≥ α^{TL},

which yields (i).

Exploiting the (ε, q)-regularity of J_{j,i+1} for every j ∈ I_{i+1} again, we observe

α − ε ≤ d_{J,q}(U, W) ≤ α + ε.  (4.46)

In order to verify the (ε^{TL}, J, q)-regularity of (U, W) it suffices to show

|d_{J,q}(U′, W′) − d_{J,q}(U, W)| ≤ ε^{TL}  (4.47)

for set U′ ⊆ U, W′ ⊆ W satisfying

|U′| = ε^{TL}|U| = ε^{TL}(1 − μ)m
|W′| = ε^{TL}|W | = ε^{TL}|I_{i+1}|m. (4.48)

For j ∈ I_{i+1} we bound the number of edges in J[U′, W′∩V_{j}] depending on the order of W′ ∩V_{j}. If |W′ ∩V_{j}| ≥ εm we are enabled to use the (ε, q)-regularity of J_{j,i+1} and derive

(α − ε)q|U′||W′ ∩ V_{j}| ≤ e(J[U′, W′ ∩ V_{j}]) ≤ (α + ε)q|U′||W′ ∩ V_{j}|. (4.49)

On the other hand, if |W′ ∩ V_{j}| < εm we use the (ξ, 3/2)-boundedness and infer

0 ≤ e(J[U′, W′ ∩ V_{j}]) ≤ \frac{3}{2}q|U′||W′ ∩ V_{j}|.  (4.50)

Clearly, we get a lower and an upper bound for e(J[U′, W′]) if we assume the ’worst case scenario’: |W′ ∩ V_{j}| < εm for as many as possible j ∈ I_{i+1}. But, since ε^{TL} ≥ \sqrt[3]{ε} > ε, at least for one j′ ∈ I_{i+1} the order of W′ ∩ V_{j} is bounded from below by |I_{i+1}|ε^{TL}m − (|I_{i+1}| − 1)εm ≥ εm. This observation accompanied by (4.48), (4.49), and (4.50) implies

(α − ε)q · ε^{TL}(1 − μ)m · (|I_{i+1}|ε^{TL}m − (|I_{i+1}| − 1)εm) ≤ e(J[U′, W′]) ≤

(|I_{i+1}| − 1) · \frac{3}{2}q · ε^{TL}(1 − μ)m · εm +

(α + ε)q · ε^{TL}(1 − μ)m · (|I_{i+1}|ε^{TL}m − (|I_{i+1}| − 1)εm) ,

which yields

(α − ε) − \frac{|I_{i+1}| − 1}{|I_{i+1}|} \frac{ε}{ε^{TL}} (α − ε)

≤ d_{J,q}(U′, W′) ≤

(α + ε) + \frac{|I_{i+1}| − 1}{|I_{i+1}|} \frac{ε}{ε^{TL}} (\frac{3}{2} − α − ε) .

Finally, we compare the lower (upper) bound from above with the upper (lower) bound from (4.46) to verify (4.47). Therefore, with our choice of ε ≤ (ε^{TL})^{3} and (4.45) we observe

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

≤ max \{|(α − ε) − \frac{|I_{i+1}| − 1}{|I_{i+1}|} \frac{ε}{ε^{TL}} (α − ε) − (α + ε)|,

|(α + ε) + \frac{|I_{i+1}| − 1}{|I_{i+1}|} \frac{ε}{ε^{TL}} (\frac{3}{2} − α − ε) − (α − ε)|\}

≤ \{2ε + \frac{ε}{ε^{TL}} , 2ε + \frac{3ε}{2ε^{TL}} \}

≤ \frac{7}{2} (ε^{TL})^{2}

≤ ε^{TL}.

Since H is d-degenerate

|I_{i+1}| ≤ d

and, thus assertion (II) for q and Claim 27 (i) and (ii) show that 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_{i+1}|}(1 − μ)m\}| ≤ η^{TL}\binom{im}{i}.

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

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

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

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

4.4.3 Main proof

Our proof of the Counting Lemma, Lemma 10, follows immediately from Lemmas 28 and 29 below. Lemma 28 is a probabilistic statement and asserts that the probability of the occurrence of the event X_{bad} = X_{1} ⊆ G(n, q) is o(1). On the other hand, Lemma 29 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 H. We apply the technical propositions from the last section in the proof of the probabilistic Lemma 28 below.

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

ℙ(G ∈ X_{bad}(γ, μ, ν, η_{1}, η_{2})) = 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_{h−2}^{(a)} ∨ (X_{h−2}^{(b)} ∧ ¬X_{h−1}) ∨ X_{h−1},

and thus, by Propositions 25 and 26 (notice X_{h−1} = X_{h−1}^{(a)} by Definition 24), we have

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

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

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

copies of H.

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

(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} that

induce H_{i} = H[{w_{1}, …, w_{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 H_{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^{∑_{j=1}^{i−1} |I_{j}|}m^{i−1} different (i − 1)-tuples b = (v_{1}, …, v_{i−1}), each constituting the vertex set of a H_{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_{i}|}m, and

(ii) d_{B_{i}}(b) < νp^{|I_{i}|}m.

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

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

(1 − γ − μ − ν)^{h}p^{∑_{j=1}^{h} |I_{j}|}m^{h} = (1 − σ)p^{e(H)}m^{h}

copies of H_{h} = H in J.

Clearly, Lemmas 28 and Lemma 29 together imply the Counting Lemma, Lemma 10.

Bibliography

[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. Erdős, Some recent results on extremal problems in graph theory. Results, Theory of Graphs (Internat. Sympos., Rome, 1966), Gordon and Breach, New York, 1967, pp. 117–123 (English); pp. 124–130 (French).

[4] , On some new inequalities concerning extremal properties of graphs, Theory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968, pp. 77–81.

[5] P. Erdős and M. Simonovits, A limit theorem in graph theory, Studia Sci. Math. Hungar 1 (1966), 51–57.

[6] P. Erdős and A. H. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946), 1087–1091.

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

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

[9] S. Gerke, H.-J. Prömel, T. Schickinger, A. Steger, and A. Taraz, K_{4}-free subgraphs of random graphs revisited, submitted for publication.

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

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

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

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

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

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

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

[17] , Szemerédi’s regularity lemma and quasi-randomness, Summer School on Algorithms and Combinatorics (tentative title), Springer, Berlin, 2001, to appear.

[18] Y. Kohayakawa, V. Rödl, and M. Schacht, The Turán theorem for random graphs, accepted for publication in Combin. Probab. Comput.

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

[20] T. Schickinger, Complete subgraphs of random graphs, Ph.D. thesis, Department of Computer Science, Techical University Munich, Germany, 2002.

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

[22] M. Simonovits, A method for solving extremal problems in graph theory, stability problems, Theory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968, pp. 279–319.

[23] T. Szabó and V. H. Vu, Turán’s theorem in sparse random graphs, submitted for publication, 2002.

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

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