Threshold functions for asymmetric Ramsey properties involving cycles

Y. Kohayakawa^{∗}

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

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

B. Kreuter

Institut für Informatik, Humboldt-Universität zu Berlin Unter den Linden 6, 10099 Berlin, Germany

            E-mail address: <kreuter@informatik.hu-berlin.de>

Abstract

We consider the binomial random graph G_{n,p} and determine a sharp threshold function for the edge-Ramsey property

G_{n,p} → (C^{ℓ_{1}}, …, C^{ℓ_{r}})

for all ℓ_{1}, …, ℓ_{r}, where C^{ℓ} denotes the cycle of length ℓ. As deterministic consequences of our results, we prove the existence of sparse graphs having the above Ramsey property as well as the existence of infinitely many critical graphs with respect to the property above.

AMS subject classification code (1991): 05C55, 05C80, 05C38 Key words and phrases: Ramsey theory, random graphs, threshold functions, Szemerédi’s lemma, cycles

1 Introduction and Results

Ramsey properties of random graphs have been investigated only recently. The aim of these investigations has been to find sharp thresholds for various Ramsey properties that a random graph may satisfy. Let us concentrate here on the binomial model of random graphs, the so-called G_{n,p}- or G_{p}-model. Thus, our random graph G_{p} = G_{n,p} has n vertices and its edges are present independently with probability p. See Bollobás [1] for details concerning random graphs and Graham, Rothschild, and Spencer [2] for Ramsey theory.

∗Partially supported by CNPq (Proc. 300334/93–1 and ProTeM-CC-II Project ProComb). Part of this work was done while this author was visiting Humboldt-Universität zu Berlin through PROBRAL project number 026/95, a CAPES–DAAD exchange programme.

The thresholds for vertex-Ramsey properties, i.e., the case in which the vertices of the random graph are coloured, were established by Łuczak, Ruciński, and Voigt [12]. The case in which edges are coloured turned out to be rather more involved, but Rödl and Ruciński [13, 14, 15] succeeded in settling this case quite recently as well. Now, the results in [12, 13, 14, 15] cover the case of symmetric Ramsey properties, that is, the case in which we seek a monochromatic copy of one given graph. Here we shall consider the asymmetric case, namely, when we have one target graph for each colour. The threshold functions for asymmetric Ramsey properties with respect to vertex colourings are determined in [10]. In this note we consider edge-Ramsey properties of G_{p} when the target graphs are cycles.

We need some definitions before we may proceed. For an integer n, we write [n] for {1, …, n}. All logarithms in this note are with respect to base e. For a graph G, we denote by V (G) and E(G) the sets of vertices and edges of G. The sizes of these sets will be abbreviated by |G| = |V (G)| and e(G) = |E(G)|. The maximum 2-density of a graph G is

m_{2}(G) = max \{\frac{e(J) − 1}{|J| − 2}: J ⊆ G with |J| ≥ 3\} .

We now recall the arrow notation for Ramsey properties. For two graphs F and H and an integer r ≥ 2, we write F → (H)_{r} to mean that in any colouring of the edges of F with r colours there is a subgraph of F isomorphic to H whose edges are all coloured by the same colour. Given r graphs H_{1}, …, H_{r}, we may generalize this definition by letting F → (H_{1}, …, H_{r}) stand for the fact that, for any colouring of the edges of F with colours 1, …, r, there is a colour i for which there is a copy of H_{i} in F whose edges are all coloured with colour i.

Using this notation, the results of Rödl and Ruciński read as follows, where P^{4} denotes the path on four vertices.

Theorem 1 Let H be a graph containing a cycle or a P^{4}. Let β = 1/m_{2}(H) and let r ≥ 2 be an integer. Then there exist constants b and B > 0 such that

(a) for p = p(n) ≤ bn^{−β} we have

P [G_{p} → (H)_{r}] = o(1),

(b) for p = p(n) ≥ Bn^{−β} we have

P [G_{p} → (H)_{r}] = 1 − o(1).

Now consider the problem of determining the threshold for the property G_{p} → (H_{1}, H_{2}). For graphs H_{1} and H_{2} with m_{2}(H_{1}) ≤ m_{2}(H_{2}), put

β = β(H_{1}, H_{2}) = min \{\frac{|J| − 2 + 1/m_{2}(H_{1})}{e(J)}: J ⊆ H_{2} with e(J) ≥ 1\} .  (1)

Observe that β is not symmetric in H_{1} and H_{2} but depends to a larger extent on the denser of the two graphs. The following theorem contains the so-called 1-statement corresponding to the case in which H_{1} is the cycle C^{ℓ} and H_{2} is an arbitrary 2-balanced graph H with m_{2}(H) > m_{2}(C^{ℓ}) = (ℓ − 1)/(ℓ − 2).

Theorem 2 Let ℓ ≥ 3 be a fixed integer, and let H be a 2-balanced graph with m_{2}(H) = (e(H) − 1)/(|H| − 2) > m_{2}(C^{ℓ}) = (ℓ − 1)/(ℓ − 2). Then there is a constant B such that, setting p = p(n) = Bn^{−β} where

β = β(C^{ℓ}, H) = \frac{|H| − 2 + 1/m_{2}(C^{ℓ})}{e(H)} = \frac{|H| − 1 − 1/(ℓ − 1)}{e(H)},  (2)

we have

P [G_{p} → (C^{ℓ}, H)] = 1 − o(1).  (3)

In the result above, the condition that H should be 2-balanced and that m_{2}(H) > m_{2}(C^{ℓ}) may be replaced by the condition that H should be strictly 2-balanced (i.e., the maximum in the definition of m_{2}(H) should be attained by H only) and that m_{2}(H) ≥ m_{2}(C^{ℓ}). The main lemma in the proof of Theorem 2, Lemma 17, concerns the number of C^{ℓ}-free graphs on n vertices fulfilling some additional properties. This lemma is a generalization of Lemma 11 from [8], which deals with the case ℓ = 3. Furthermore, Lemma 17 may be used to unify the proofs of the results in [3] and [4]. However, the main result from [7], which is similar in spirit, does not follow from Lemma 17.

The next theorem says that the exponent β in Theorem 2 is involved in the corresponding 0-statement, thus establishing a sharp threshold for the property G_{p} → (C^{ℓ}, C^{k}).

Theorem 3 Let 3 ≤ k ≤ ℓ be integers, and let

β = β(C^{ℓ}, C^{k}) = \frac{(k − 1)(ℓ − 1) − 1}{k(ℓ − 1)} = 1 − \frac{ℓ}{k(ℓ − 1)}.

Then there exists a constant b > 0 such that, for p = p(n) = bn^{−β}, we have

P [G_{p} → (C^{ℓ}, C^{k})] = o(1).

We shall also sketch the proof of the following generalized version of Theorem 2.

Theorem 4 Let 3 ≤ ℓ_{2} ≤ ⋯ ≤ ℓ_{r} (r ≥ 2) be integers, and suppose H is a 2-balanced graph with m_{2}(H) > m_{2}(C^{ℓ_{2}}). Let β = β(C^{ℓ_{2}}, H). Then there are constants B and κ > 0 such that, for p = p(n) = Bn^{−β}, almost every G_{p} satisfies the property that any subgraph G′ ⊆ G_{p} of G_{p} with e(G′) ≥ e(G_{p}) − κn^{1+1/(ℓ_{2}−1)}/(log n)^{|H|} is such that

G′ → (H, C^{ℓ_{2}}, …, C^{ℓ_{r}}).

Similarly to the case of Theorem 2, the result above also holds if H is strictly 2balanced and m_{2}(H) = m_{2}(C^{ℓ_{2}}). We further remark that the log-factor in the number of edges that one is allowed to delete from G_{p} can be got rid of.

The following result is an immediate corollary to Theorems 3 and 4.

Corollary 5 Let 3 ≤ ℓ_{1} ≤ ⋯ ≤ ℓ_{r} (r ≥ 2) be integers, and let β = β(C^{ℓ_{2}}, C^{ℓ_{1}}). Then there exist constants b and B > 0 such that

(a) for p = p(n) ≤ bn^{−β} we have

P [G_{p} → (C^{ℓ_{1}}, …, C^{ℓ_{r}})] = o(1),

(b) for p = p(n) ≥ Bn^{−β} we have

P [G_{p} → (C^{ℓ_{1}}, …, C^{ℓ_{r}})] = 1 − o(1).

It would be interesting to determine the threshold functions for the properties G_{p} → (H_{1}, H_{2}) for arbitrary graphs H_{1} and H_{2}, or more generally for the analogous problem when more than two graphs are involved. We formulate the following conjecture.

Conjecture 6 Let H_{1}, H_{2} be graphs with m_{2}(H_{1}) ≤ m_{2}(H_{2}) and let β = β(H_{1}, H_{2}) be as defined in (1). Then p = p(n) = n^{−β} is a sharp threshold for the property G_{p} → (H_{1}, H_{2}).

Unfortunately, the techniques used in this note are by far not sufficient to yield a proof of this more general case.

We now single out two deterministic consequences of our methods. Let integers t, ℓ_{2} ≥ 3 and a graph H be given. Let V_{ℓ_{2},H,t} be the class of graphs F with at most t vertices satisfying |F | − β(C^{ℓ_{2}}, H)e(F) < 1 + 1/(ℓ_{2} − 1).

Corollary 7 For any fixed integers 3 ≤ ℓ_{2} ≤ ⋯ ≤ ℓ_{r} (r ≥ 2) and t ≥ 1 and any 2-balanced graph H with m_{2}(H) > m_{2}(C^{ℓ_{2}}), there is a graph G that satisfies G → (H, C^{ℓ_{2}}, …, C^{ℓ_{r}}) and contains no member of V_{ℓ_{2},H,t}.

An immediate consequence of the corollary above is that, for any 3 ≤ ℓ_{1} ≤ ⋯ ≤ ℓ_{r}, there are graphs G of girth ℓ_{1} satisfying G → (C^{ℓ_{1}}, …, C^{ℓ_{r}}).

Our second deterministic result states that the r-tuple (C^{ℓ_{1}}, …, C^{ℓ_{r}}) is Ramsey-infinite for any ℓ_{1}, …, ℓ_{r} ≥ 3. A graph G is called Ramsey-critical, or simply critical, for an rtuple of graphs (H_{i})_{1≤i≤r} (r ≥ 2) if G → (H_{i})_{1≤i≤r} but, for any proper subgraph G′ ⊂ G of G, the relation G′ → (H_{i})_{1≤i≤r} fails. The r-tuple (H_{i})_{1≤i≤r} is called Ramsey-finite if the class of all graphs that are critical for (H_{i})_{1≤i≤r} is finite and Ramsey-infinite otherwise. If (H_{i})_{1≤i≤r} is Ramsey-finite then there clearly is a polynomial time algorithm that, given a graph G, decides whether or not G → (H_{i})_{1≤i≤r} holds.

Corollary 2 of [15] implies that the pair (H, H) is Ramsey-infinite for any graph H containing a cycle, and Łuczak [11] showed that the pair (F, H) is Ramsey-infinite if F is a forest and H contains a cycle. Our result is as follows.

Theorem 8 For any 3 ≤ ℓ_{1} ≤ ⋯ ≤ ℓ_{r} (r ≥ 2), the r-tuple (C^{ℓ_{i}})_{1≤i≤r} is Ramsey-infinite.

The organisation of this note is as follows. In Section 2 we give the proof of Theorem 2 and sketch the proof of Theorem 4. Theorem 3 is proved in Section 3. The deterministic consequences are proved in Section 4.

2 The proofs of Theorems 2 and 4

We shall need a fair amount of preparation to prove Theorems 2 and 4. In Sections 2.1 and 2.2, we set out some well known lemmas and some preliminary results that we shall need. In Section 2.3, we prove our crucial lemma, Lemma 17.

2.1 Basic tools

2.1.1 Janson’s inequality

Let E be a finite set. Let (J_{e})_{e∈E} be a family of independent random indicator variables indexed by E such that E(J_{e}) = p for all e ∈ E. Suppose (E_{α})_{α∈A} is a family of subsets of E. Let I_{α} = ∏_{e∈E_{α}} J_{e}, and S = ∑_{α∈A} I_{α}. Thus, the random variable S counts how many of the sets E_{α} (α ∈ A) have all its elements e ∈ E_{α} such that J_{e} = 1. Let

Δ = ∑_{α,β} E(I_{α}I_{β}),  (4)

where the sum extends over all ordered pairs (α, β) with α ≠ β but E_{α} ∩E_{β} ≠ ∅. Janson’s inequality [5] is then the following.

Lemma 9 For all 0 ≤ ε ≤ 1, writing μ = E(S), we have

P[S ≤ (1 − ε)μ] ≤ exp \{−\frac{1}{2(1 + Δ/μ)}ε^{2}μ\} .  (5)

2.1.2 Szemerédi’s lemma

The following notions will be needed in what follows. Let a graph J be fixed. In the sequel we let V = V (J). Suppose 0 < η ≤ 1, D > 1, and 0 < p ≤ 1. We say that J is (η, D, p)-upper-uniform if for all U, W ⊆ V with U ∩ W = ∅ and |U|, |W | ≥ ηn, we have e_{J}(U, W) ≤ Dp|U||W |. In the sequel, for any two disjoint non-empty sets U, W ⊆ V, let the p-density of J between U and W be

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

Now suppose 0 < ε ≤ 1 is a real number, and U, W ⊆ V are two non-empty disjoint sets of vertices of J. We say that the pair (U, W) is (ε, J, p)-regular if for all U′ ⊆ U, W′ ⊆ W with |U′| ≥ ε|U| and |W′| ≥ ε|W | we have

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

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

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

2.1.3 Nearly regular subgraphs

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

Now suppose we have real numbers 0 < p ≤ 1, 0 < ε ≤ 1, and 0 < γ_{0} ≤ 1. Let also m_{i} = |U_{i}| (1 ≤ i ≤ t), and write γ_{ij} for the p-density d_{J,p}(U_{i}, U_{j}) for all distinct i and j. Suppose the pair (U_{i}, U_{i+1}) is (ε, J, p)-regular and γ_{i,i+1} ≥ γ_{0} for any 1 ≤ i < t.

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

Lemma 11 Let J and the sets U_{i} (1 ≤ i ≤ t) be as above. Suppose 0 < ε ≤ 1/5 and put A = 4 + 1/γ_{0}. Then there are sets Ū_{i} ⊆ U_{i} with |Ū_{i}| ≥ (1 − 4ε)m_{i} for all 1 ≤ i ≤ t such that, for all i, j ∈ [t] with |i − j| = 1 and any x ∈ Ū_{i}, we have

d_{ij}(x) = |Γ_{J}(x) ∩ Ū_{j}| = (1 + O_{1}(Aε))γ_{ij}pm_{j}.

Lemma 11 above is very similar to Lemma 2 from [8] and Lemma 5 from [9], and hence its proof is omitted.

2.1.4 Ramsey’s theorem

Here we give the following easy consequence of Ramsey’s theorem.

Lemma 12 Let graphs H_{1}, …, H_{r} (r ≥ 1) be given. Then there exist positive constants c = c(H_{1}, …, H_{r}) > 0 and k_{0} = k_{0}(H_{1}, …, H_{r}) for which the following holds. If k ≥ k_{0} and K^{k} is given an arbitrary r-edge-colouring, then we necessarily have, for some 1 ≤ i ≤ r, at least ck^{|H_{i}|} monochromatic copies of H_{i} of colour i.

Proof. Let k_{0} = q and c = (1/r)q^{− max_{i} |H_{i}|}, where

q = R(H_{1}, …, H_{r}) = min{n: K^{n} → (H_{1}, …, H_{r})},

the Ramsey number for (H_{1}, …, H_{r}). Now let K^{k} with k ≥ k_{0} be given an arbitrary redge-colouring. Then, each q-subset of the vertex set of K^{k} gives, for some i, a monochromatic copy of H_{i} of colour i. For some i, at least (1/r)\binom{k}{q} of these q-subsets gives a monochromatic H_{i} of colour i. Each such copy is counted at most \binom{k−|H_{i}|}{q−|H_{i}|} times. The number of such copies is, therefore, at least

\frac{1}{r}\binom{k}{q} /\binom{k − |H_{i}|}{q − |H_{i}|} = \frac{1}{r} \frac{(k)_{|H_{i}|}}{(q)_{|H_{i}|}} ≥ \frac{1}{r} (\frac{k}{q} )^{|H_{i}|} ≥ ck^{|H_{i}|},

as required. □

2.2 Preliminary lemmas

Throughout this section we fix an integer ℓ ≥ 3 and a graph H as in the statement of Theorem 2. Moreover, here we shall always suppose that p = p(n) = Bn^{−β}, where β is as defined in (2) and B > 0 is some constant. We also sometimes write h for the order of our graph H. For the sake of definiteness, we shall assume that V (G_{p}) = [n].

If H_{1} is a copy of H in G_{p} we say that H_{1} is isolated if it does not intersect any other copy of H present in G_{p} on an edge. In other words, if we have E(H_{1}) ∩ E(H_{2}) = ∅ for any other copy H_{2} of H in G_{p}.

2.2.1 Isolated copies of H in G_{p}

Let us write T = T (G_{p}) for the number of isolated copies of H in G_{p}. Let h = |H|. Using the fact that H is 2-balanced and that m_{2}(C^{ℓ}) < m_{2}(H), it is easy to see that almost all copies of H in G_{p} are isolated but we shall not need this here. Let us write p_{0} for the expected number of (not necessarily isolated) copies of H in G_{p} that contain some fixed edge e ∈ \binom{[n]}{2}. Clearly, the expected number μ_{H} of copies of H in G_{p} is |Aut(H)|^{−1}(n)_{h}p^{e(H)}, where Aut(H) denotes the automorphism group of H. A moment’s thought then shows that

p_{0} = \frac{(n)_{h}e(H)}{|Aut(H)|\binom{n}{2}}p^{e(H)} = (2 + o(1))\frac{e(H)B^{e(H)}}{|Aut(H)|} n^{−1+1/(ℓ−1)}.  (6)

We now consider the following construction we shall use later. Let H = {H_{1}, …, H_{T} } be the set of isolated copies of H in G_{p}. We shall always write H̃ = H̃(G_{p}) for the spanning subgraph of G_{p} whose edge set is the union of the edge sets of the H_{i} (1 ≤ i ≤ T). Clearly, we have e(H̃) = T e(H).

If we denote by p̃ the probability that a given edge e ∈ \binom{[n]}{2} is contained in H̃ then p̃ = (1 + o(1))p_{0} as almost all copies of H are isolated. In the sequel we shall only use p_{0}, which may be considered to be the edge probability of H̃.

Next we show that the edges of H̃ satisfy some negative correlation properties. For E ⊆ \binom{[n]}{2}, write E ⊏ E(H̃) if E ⊆ E(H̃) and all edges from E belong to different isolated copies of H in G_{p}.

Lemma 13 For any set E ⊆ \binom{[n]}{2},

P[E ⊏ E(H̃)] ≤ p_{0}^{|E|}.

Proof. Suppose E = {e_{1}, …, e_{a}} where a = |E|. Let I be the set of all a-tuples (H_{1}, …, H_{a}) of H-subgraphs of K^{n} with e_{i} ∈ E(H_{i}) for all 1 ≤ i ≤ a. Also, let J be the set of such a-tuples (H_{1}, …, H_{a}) ∈ I with the H_{i} (1 ≤ i ≤ a) pairwise edge-disjoint. Finally, let H_{i} be set of H-subgraphs of K^{n} that contain the edge e_{i} (1 ≤ i ≤ a). Thus, in particular, I = H_{1} × ⋯ × H_{a}. Then

P[E ⊏ E(H̃)] ≤ ∑_{(H_{1},...,H_{a})∈J} P[H_{1} ⊆ G_{p}, …, H_{a} ⊆ G_{p}]
= ∑_{(H_{1},...,H_{a})∈J} P[H_{1} ⊆ G_{p}] ⋯ P[H_{a} ⊆ G_{p}]
≤ ∑_{(H_{1},...,H_{a})∈I} P[H_{1} ⊆ G_{p}] ⋯ P[H_{a} ⊆ G_{p}]

= ∑_{H_{1}∈H_{1}} P[H_{1} ⊆ G_{p}] ⋯ ∑_{H_{a}∈H_{a}} P[H_{a} ⊆ G_{p}]
= p_{0}^{a},

as required. □

2.2.2 Upper-uniformity results for H̃

In this section we show that the edges of H̃ are fairly well distributed in the sense that H̃ is, almost surely, locally sparse. Our first lemma implies that almost every H̃ is (η, 3e(H), p_{0})- upper-uniform for any fixed 0 < η ≤ 1.

Lemma 14 Let ω = ω(n) → ∞ as n → ∞. Then, for almost every G_{p}, the graph H̃ = H̃(G_{p}) is such that the following holds. Suppose U, W ⊆ V (H̃) with U ∩ W = ∅ are such that |U||W | ≥ ωn^{2−1/(ℓ−1)}. Then we have

e_{H}(U, W) ≤ 3e(H)p_{0}|U||W |.  (7)

Proof. If a fixed pair (U, W) with u = |U| and w = |W | does not satisfy (7) then there is a set E ⊆ U × W with E ⊆ E(H̃) and |E| = ⌈3e(H)p_{0}uw⌉. This implies the existence of a set E′ ⊆ U × W of size |E′| = ⌈3p_{0}uw⌉ such that all edges from E′ belong to different isolated copies of H in G_{p}. The probability of this event is by Lemma 13 at most

\binom{uw}{⌈3p_{0}uw⌉}p_{0}^{⌈3p_{0}uw⌉} ≤ (\frac{e}{3})^{3p_{0}uw} .

As there are at most 2^{2n} choices for the sets U and W, the lemma follows from the fact that 3p_{0}uw/n → ∞ as n → ∞ (cf. (6)). □

Our next lemma concerns the number of H̃-edges between sets U and W smaller than the ones considered in Lemma 14, and hence may be thought of as a more local condition on the sparseness of H̃. To state our lemma concisely, we introduce a definition. Let J be a graph on n vertices and suppose C ≥ 1 and ℓ ≥ 1 are given. We say that J is locally (p_{0}, C, ℓ)-upper-uniform if for all pairs (U, W) of disjoint sets of vertices U, W ⊆ V (J) satisfying

|U| ≤ |W | ≤ d_{0}|U| ≤ d_{0}^{ℓ−2},  (8)

where d_{0} = p_{0}n, we have

e_{J}(U, W) ≤ C|W |.  (9)

Lemma 15 Almost every G_{p} is such that H̃ = H̃(G_{p}) is locally (p_{0}, 2ℓe(H), ℓ)-upper uniform.

Proof. The probability that a fixed pair (U, W) of disjoint sets of vertices with u = |U| and w = |W | does not satisfy (9) can be bounded similarly as in the proof of Lemma 14 by

\binom{uw}{⌈2ℓw⌉}p_{0}^{⌈2ℓw⌉} ≤ (\frac{eu}{2ℓ}p_{0})^{2ℓw} .

Observe that, for pairs (U, W) as in (8), we have u ≤ (p_{0}n)^{ℓ−3} ≤ An^{(ℓ−3)/(ℓ−1)} for some constant A = A(H, B) > 0. Moreover, we have u ≤ w = o(n) as n → ∞, and hence \binom{n}{u}\binom{n}{w} ≤ \binom{n}{w}^{2}. Therefore, the expected number of pairs (U, W) satisfying (8) but not (9) is at most

∑_{w=1}^{⌊n/2⌋} w\binom{n}{w}^{2} (\frac{eu}{2ℓ}p_{0})^{2ℓw} ≤ ∑_{w=1}^{⌊n/2⌋} w (n^{1/ℓ} \frac{e^{1+1/ℓ}}{2ℓ} An^{(ℓ−3)/(ℓ−1)}p_{0})^{2ℓw} = o(1)

(cf. (6)) and the lemma follows from Markov’s inequality. □

2.2.3 The distribution of isolated copies of H in G_{p}

In this section we prove a simple lemma concerning the existence of a large number of isolated copies of H in G_{p} when p is as given in Theorem 2. In fact, for technical reasons, we shall need to look at the existence of such copies of H with each of their vertices taken from specified subsets of vertices of G_{p}.

Label the vertices of H by v_{1}, …, v_{h} where h = |H|. Suppose W_{1}, …, W_{h} are pairwise disjoint subsets of vertices of G_{p}. Put W = (W_{i})_{i=1}^{h}. Here we are interested in the number Z = Z_{W}(G_{p}) of injections ι: V (H) → V (G_{p}) taking v_{i} into W_{i} for all 1 ≤ i ≤ h, and such that ι(v_{i})ι(v_{j}) ∈ E(G_{p}) whenever v_{i}v_{j} ∈ E(H). We shall refer to such maps ι as W-embeddings of H in G_{p}. Moreover, we say that the subgraph of G_{p} with vertex set ι(V (H)) and edge set {ι(v_{i})ι(v_{j}): v_{i}v_{j} ∈ E(H)} is the image im ι of ι.

Finally, let us define Y = Y_{W}(G_{p}) to be the number of W-embeddings ι of H in G_{p} with im ι an isolated H-subgraph of G_{p}.

Lemma 16 Suppose B > 0 is a constant and β is as defined in (2). Then, for p = Bn^{−β}, almost every G_{p} has the following property. For any vector W = (W_{i})_{i=1}^{h} of pairwise disjoint sets W_{i} ⊆ [n] (1 ≤ i ≤ h), each of cardinality at least n/ log n, we have Y = Y_{W}(G_{p}) ≥ (1/2)E(Z_{W}).

Proof. Define U to be the set of all graphs that can be written as a union of two copies of H intersecting in at least one edge, not including H itself. Let then X = X(G_{p}) count the number of graphs from U present in G_{p}. We first aim at bounding X. From m_{2}(C^{ℓ}) < m_{2}(H) it is easy to see that β > 1/m_{2}(H). Let δ = β − 1/m_{2}(H) > 0. As H is 2-balanced we have that for any proper subgraph J of H containing at least one edge

\frac{|H| − |J|}{e(H) − e(J)} ≤ \frac{1}{m_{2}(H)} = β − δ.

Therefore, writing ∑_{K^{2}⊆J⊂H} for the sum over all proper subgraphs J ⊂ H containing at least one edge, we have

E(X) = ∑_{U∈U} \frac{(n)_{|U|}}{|Aut(U)|}p^{e(U)}
= O( ∑_{K^{2}⊆J⊂H} n^{2|H|−|J|}p^{2e(H)−e(J)})

= O( ∑_{K^{2}⊆J⊂H} n^{2|H|−|J|−β(2e(H)−e(J))})
= O (n^{|H|−βe(H)−δ(e(H)−e(J))})
= O(n^{1+1/(ℓ−1)−δ(e(H)−e(J))}).

Next we use Janson’s inequality (5) to show that Z_{W} is with high probability not too small. So fix W = (W_{i})_{i=1}^{h} and let (H_{α}: α ∈ A) be the family of all graphs which are isomorphic to H and whose vertex set can be written as {v_{1}, …, v_{h}} with v_{i} ∈ W_{i} for all 1 ≤ i ≤ h. Thus |A| = |W_{1}| … |W_{h}| ≥ (n/ log n)^{h}, and the random variable S defined in Section 2.1.1 coincides with Z_{W}. We have that

E(Z_{W}) ≥ (\frac{n}{log n})^{|H|} B^{e(H)}n^{−βe(H)} = B^{e(H)}n^{1+1/(ℓ−1)−|H| log log n/ log n}.

By Markov’s inequality we have that X = o(E(Z_{W})) almost surely and therefore also Δ ≤ 2X = o(E(Z_{W})) where Δ is as defined in (4). Then Janson’s inequality implies that

P [Z_{W} ≤ \frac{3}{4}E(Z_{W})] ≤ exp (−\frac{1}{33}E(Z_{W})) ≤ exp(−n^{1+1/ℓ}),

if n is large enough. On the other hand, there are at most 2^{hn} choices for W. Thus for almost every G_{p} we have Z_{W} ≥ (3/4)E(Z_{W}) for every W. Furthermore we almost surely have that X ≤ E(Z_{W})/8 and therefore also Y_{W}(G_{p}) ≥ Z_{W} − 2X ≥ E(Z_{W})/2 for every W, almost surely, as required. □

2.3 The key counting lemma

Throughout this section, ℓ ≥ 3 is a fixed integer and V = (V_{1}, …, V_{ℓ}) is a fixed vector of pairwise disjoint sets V_{1}, …, V_{ℓ}, all of the same cardinality, say m.

In this section we shall be interested in counting certain graphs F whose vertex set is V (F) = ⋃_{i=1}^{ℓ} V_{i} and all whose edges join vertices in consecutive classes V_{i}. More precisely, if e is an edge of F, then its two endpoints will belong to V_{i−1} and V_{i}, respectively, for some 1 ≤ i ≤ ℓ. Here and below, the indices of the sets V_{i} will be taken modulo ℓ. For conciseness, given V = (V_{i})_{i=1}^{ℓ}, let us say that a graph F as described above is a V-graph. To define the precise subclass of V-graphs F that we shall be interested in, however, we need to introduce some more parameters and definitions.

Let 0 < ε ≤ 1, B̄ > 0, 0 < γ_{0} ≤ 1, C ≥ 1, and D ≥ 1 be real numbers and let T̄ be a positive integer. We shall write

F_{m}(ε, B̄, γ_{0}, C, D; V, T̄)

for the set of V-graphs F satisfying conditions (i)–(iv) given below.

(i) The graph F has T̄ edges. (ii) The graph F is such that all the pairs (V_{i−1}, V_{i}) (1 ≤ i ≤ ℓ) are (ε, F, p̄)-regular,

where p̄ = p̄(m) = B̄m^{−1+1/(ℓ−1)}. (iii) The p̄-density γ_{i−1,i} = d_{F,p̄}(V_{i−1}, V_{i}) of F between the sets V_{i−1} and V_{i} is such that,

for all 1 ≤ i ≤ ℓ, we have

γ_{0} ≤ γ_{i−1,i} ≤ D.  (10)

(iv) For all U ⊆ V_{i−1} and W ⊆ V_{i} (2 ≤ i < ℓ) with

|U| ≤ |W | ≤ d̄|U| ≤ d̄^{ℓ−2},  (11)

where d̄= p̄m, we have

e_{F} (U, W) ≤ C|W |.  (12)

Let us now define the class

F′_{m}(ε, B̄, γ_{0}, C, D; V, T̄) ⊆ F_{m}(ε, B̄, γ_{0}, C, D; V, T̄)

as the class of graphs F ∈ F_{m}(ε, B̄, γ_{0}, C, D; V, T̄) that do not contain a copy of C^{ℓ} as a subgraph. Our aim in this section is to estimate the cardinality f′_{m}(ε, B̄, γ_{0}, C, D; T̄) of F′_{m}(ε, B̄, γ_{0}, C, D; V, T̄) from above.

Lemma 17 Let an integer ℓ ≥ 3 be fixed, and let constants 0 < α ≤ 1, 0 < γ_{0} ≤ 1, C ≥ 1, and D ≥ 1 be given. Then there are constants 0 < ε ≤ 1, B̄_{0} > 0, and m_{0} that depend only on ℓ, α, γ_{0}, C, and D such that, for all integers m ≥ m_{0} and T̄ ≥ 1 and real numbers B̄ ≥ B̄_{0}, we have

f′_{m}(ε, B̄, γ_{0}, C, D; T̄) ≤ αT̄\binom{(ℓ + 2)m^{2}}{T̄}.  (13)

The proof of Lemma 17 is based on a technical lemma, Lemma 18, that we now describe. Let a constant 0 < δ ≤ 1 be given, and suppose we have real numbers 0 < ε ≤ 1, 0 < γ_{0} ≤ 1, B̄, C, D ≥ 1, and an integer T̄ ≥ 1. Let

F ∈ F_{m}(ε, B̄, γ_{0}, C, D; V, T̄)

be fixed. Lemma 18 will concern the (ℓ − 1)-partite subgraph Ḟ = F [V_{1}, …, V_{ℓ−1}] of F induced by the vertex classes V_{1}, …, V_{ℓ−1}. Suppose y_{1}, …, y_{j−1} ∈ V_{1} are j − 1 given vertices of V_{1}, where 1 ≤ j ≤ δm/2. Let

U_{1} = V_{1} \ {y_{1}, …, y_{j−1}}  (14)

and

U_{ℓ−1} = V_{ℓ−1} \ ⋃_{q=1}^{j−1} Γ̇_{F}^{(ℓ−2)}(y_{q}),  (15)

where Γ̇_{F}^{(ℓ−2)} denotes the (ℓ − 2)-fold iteration of Γ̇_{F} = ΓḞ. Suppose |U_{ℓ−1}| ≥ δm. Our technical lemma tells us that then, provided ε is small enough, most vertices in U_{1} are ‘good’, in the sense that their (ℓ − 2)nd Ḟ -neighbourhood within U_{ℓ−1} is large.

Lemma 18 Let 0 < δ ≤ 1, 0 < γ_{0} ≤ 1, B̄ > 0, C ≥ 1, and D ≥ 1 be given. Then if 0 < ε ≤ min{δ/4, γ_{0}/(8γ_{0} + 2)}, and m and T̄ are integers, any graph F ∈ F_{m}(ε, B̄, γ_{0}, C, D; V, T̄) is such that at least (1 − δ)|U_{1}| vertices y ∈ U_{1} satisfy

|Γ̇_{F}^{(ℓ−2)}(y) ∩ U_{ℓ−1}| ≥ 2^{−ℓ+2} \frac{γ_{0}^{ℓ−2}}{C^{ℓ−3}} δd̄^{ℓ−2},  (16)

where d̄= p̄m.

Proof of Lemma 17. Let ℓ, α, γ_{0}, C, and D as in the statement of our lemma be given. Let us define the constants

δ = min{1/2, (α^{ℓD}2^{−5D})^{8/γ_{0}}},
ε = min{δ/4, γ_{0}/(8γ_{0} + 2)},
B̄_{0} = (\frac{4C^{ℓ−3}}{2^{−ℓ+2}γ_{0}^{ℓ−1}δ} )^{1/(ℓ−1)} ,

m_{0} = (\frac{3}{2}DB̄_{0})^{(ℓ−1)/(ℓ−2)} .

Our aim is to show that ε, B̄_{0} and m_{0} given above will do in Lemma 17. Thus, let integers m ≥ m_{0} and T̄ and a real B̄ ≥ B̄_{0} be given. We have to show that (13) holds. We estimate f′_{m}(ε, B̄, γ_{0}, C, D; T̄) from above by estimating the number of ways we may ‘generate’ an element from F′_{m}(ε, B̄, γ_{0}, C, D; V, T̄).

In order to generate a graph F from F′_{m}(ε, B̄, γ_{0}, C, D; V, T̄), we first choose T̄_{1} = e_{F} (V_{1}, V_{ℓ}) and T̄_{ℓ−1} = e_{F} (V_{ℓ−1}, V_{ℓ}). Later on we shall sum over all possible values of T̄_{1} and T̄_{ℓ−1}. Observe that for i ∈ {1, ℓ} we have

γ_{0}B̄m^{1+1/(ℓ−1)} ≤ T̄_{i} = d_{F,p̄}(V_{i}, V_{ℓ})p̄m^{2} ≤ DB̄m^{1+1/(ℓ−1)}.  (17)

Put T̄_{0} = T̄ − T̄_{1} − T̄_{ℓ−1}. Next we fix Ḟ = F [V_{1}, …, V_{ℓ−1}], for which we have not more than \binom{(ℓ−2)m^{2}}{T̄_{0}} possibilities. By Lemma 11 for t = 3, we know that for any choice of the edges of F incident to V_{ℓ} there have to be sets V̄_{i} ⊆ V_{i} (i ∈ {1, ℓ − 1, ℓ}) such that for any x ∈ V̄_{ℓ} and any i ∈ {1, ℓ − 1} we have

d_{i}(x) = |Γ_{F} (x) ∩ V̄_{i}| = (1 + O_{1}(Aε))\frac{T̄_{i}}{p̄|V_{ℓ}||V_{i}|}p̄|V_{i}| = (1 + O_{1}(Aε))\frac{T̄_{i}}{m},  (18)

where A = 4 + 1/γ_{0}. Call the F -edges in V̄_{ℓ} × V̄_{i} (i ∈ {1, ℓ − 1}) regular edges and the remaining F -edges between V_{ℓ} and V_{i} irregular edges. For i ∈ {1, ℓ − 1}, denote by T̄_{i}^{(irr)} the number of irregular edges incident to V_{i}. Summing up we have that, for given T̄_{0} and T̄_{i}^{(irr)}, there are at most

\binom{(ℓ − 2)m^{2}}{T̄_{0}}\binom{m^{2}}{T̄_{1}^{(irr)}}\binom{m^{2}}{T̄_{ℓ−1}^{(irr)}}  (19)

ways of choosing the set of edges of F, except for the regular edges incident to V_{ℓ}.

Now we have to bound the number of choices for the regular edges. Let us first choose the degree sequences (d_{i}(x))_{x∈V_{ℓ}} of the vertices in V_{ℓ}, where d_{i}(x) = |Γ_{F} (x) ∩ V̄_{i}| for i ∈ {1, ℓ − 1}. For a vertex x ∈ V̄_{ℓ} we may assume by (17), (18) and the definition of m_{0} that

d_{min} := \frac{1}{2}γ_{0}B̄m^{1/(ℓ−1)} ≤ d_{i}(x) ≤ m.  (20)

Let us now fix a vertex x in V̄_{ℓ}, and let us say that a set Y ⊆ V_{1} of size d_{min} ≤ d′ = |Y | ≤ m is good if |Γ̇_{F}^{(ℓ−2)}(Y) ∩ V_{ℓ−1}| ≥ (1 − δ)m. The idea is that if we choose a good set Y to be the neighbourhood of x within V_{1}, then the number of vertices in V_{ℓ−1} that are allowed to be adjacent to x in F is very small, namely, at most δm, since we are supposed to generate a C^{ℓ}-free graph F. Now, if a d′-set Y ⊆ V_{1} as above is not good then, for any ordering y_{1}, y_{2}, …, y_{d′} of the vertices of Y, there are at least d′/2 indices i with

|Γ̇_{F}^{(ℓ−2)}(y_{i}) \ ⋃_{q=1}^{i−1} Γ̇_{F}^{(ℓ−2)}(y_{q})| < \frac{(1 − δ)m}{d′/2} ≤ 2^{−ℓ+2} \frac{γ_{0}^{ℓ−2}}{C^{ℓ−3}} δd̄^{ℓ−2},

where the last inequality follows from the definition of B̄_{0} and (20). For these indices i, by Lemma 18, there are only δm choices for y_{i} once y_{1}, …, y_{i−1} are chosen. Therefore the number of bad sets Y of size d_{min} ≤ d′ ≤ m is at most

\binom{d′}{⌈d′/2⌉}δ^{d′/2} \frac{m^{d′}}{d′!} ≤ 2^{d′}δ^{d_{min}/2}e^{d′} \binom{m}{d′}.

If the neighbourhood Γ_{F} (x) ∩ V_{1} of the vertex x ∈ V̄_{ℓ} in V_{1} is good then, since C^{ℓ} ⊈ F, there are only \binom{δm}{d_{ℓ−1}(x)} ≤ δ^{d_{ℓ−1}(x)}\binom{m}{d_{ℓ−1}(x)} choices for the neighbourhood Γ_{F} (x) ∩ V_{ℓ−1} of x within V_{ℓ−1}. On the other hand, if Γ_{F} (x) ∩ V_{1} happens to be bad, then trivially there are at most \binom{m}{d_{ℓ−1}(x)} choices for this neighbourhood. Therefore there are at most

\binom{m}{d_{1}(x)}δ^{d_{ℓ−1}(x)}\binom{m}{d_{ℓ−1}(x)} + δ^{d_{min}/2}2^{3d_{1}(x)}\binom{m}{d_{1}(x)}\binom{m}{d_{ℓ−1}(x)}

≤ δ^{d_{min}/2}2^{3d_{1}(x)+1}\binom{m}{d_{1}(x)}\binom{m}{d_{ℓ−1}(x)}

ways of choosing the regular edges incident to our vertex x ∈ V̄_{ℓ}.

Let us write ∑′ ; T̄ for the sum over all partitions T̄_{0} + T̄_{1} + T̄_{ℓ−1} = T̄ of T̄, and similarly ∑′ ; T̄_{1} and ∑′ ; T̄_{ℓ−1} for the sums over all partitions T̄_{1}^{(irr)} + d_{1} + … + d_{m} = T̄_{1} of T̄_{1}

and T̄_{ℓ−1}^{(irr)} + d′_{1} + … + d′_{m} = T̄_{ℓ−1} of T̄_{ℓ−1}. Let us also write ∑V̄_{ℓ} for the sum over all possible choices of V̄_{ℓ}. Then, recalling the bound (19), we see that f′_{m}(ε, B̄, γ_{0}, C, D; T̄) is at most

∑′ ; T̄ ∑′ ; T̄_{1} ∑′ ; T̄_{ℓ−1} ∑V̄_{ℓ} \binom{(ℓ − 2)m^{2}}{T̄_{0}}\binom{m^{2}}{T̄_{1}^{(irr)}}\binom{m^{2}}{T̄_{ℓ−1}^{(irr)}}

×δ^{|V̄_{ℓ}|d_{min}/2} ∏_{j=1}^{m} (2^{3d_{j}+1}\binom{m}{d_{j}}\binom{m}{d′_{j}})

≤ δ^{md_{min}/4}2^{3T̄_{1}+2m}\binom{(ℓ + 2)m^{2}}{T̄} ≤ αT̄\binom{(ℓ + 2)m^{2}}{T̄},

where we apply Vandermonde’s identity and the fact that, trivially, there are at most 2^{m} choices for V̄_{ℓ} to deduce the first inequality and we use (17), (20), that T̄ ≤ ℓDB̄m^{1+1/(ℓ−1)}, and the definition of δ to deduce the second inequality. □

Proof of Lemma 18. Let ε, B̄, γ_{0}, C, D, and T̄ be as in the statement of our lemma. Fix a graph F ∈ F_{m}(ε, B̄, γ_{0}, C, D; V, T̄) and let us consider Ḟ = F [V_{1}, …, V_{ℓ−1}]. Recall (14) and (15) and put U_{i} = V_{i} for all 2 ≤ i ≤ ℓ − 2. The first step is to apply Lemma 11 with t = ℓ − 1 to get rid of vertices of small degree. We obtain sets Ū_{i} ⊆ U_{i} (1 ≤ i < ℓ) with

|Ū_{i}| ≥ (1 − 4ε)|U_{i}| ≥ (1 − δ)|U_{i}|  (21)

for all 1 ≤ i < ℓ, and such that, for all 2 ≤ i < ℓ and all x ∈ Ū_{i−1}, we have

d_{i−1,i}(x) = |Γ_{F} (x) ∩ Ū_{i}|
≥ (1 − (\frac{4γ_{0} + 1}{γ_{0}}) ε) d_{F,p̄}(U_{i−1}, U_{i})p̄|U_{i}|
≥ (γ_{0}/2)p̄|U_{i}|.  (22)

In the case ℓ = 3 we are already finished if we let i = 2 in (22). If ℓ > 3 we use property (iv) of F to prove the following assertion by induction on i.

Claim 1 For any y ∈ Ū_{1} and any 2 ≤ i ≤ ℓ − 2, we have

|Γ̇_{F}^{(i−1)}(y) ∩ Ū_{i}| ≥ 2^{−i+1} \frac{γ_{0}^{i−1}}{C^{i−2}} d̄^{i−1}.

The claim for i = 2 is just (22). For 2 < i ≤ ℓ − 2, let U ⊆ Γ̇_{F}^{(i−2)}(y) ∩ Ū_{i−1} be a set of size ⌈2^{−i+2}γ_{0}^{i−2}C^{−i+3}d̄^{i−2}⌉. Assume that W = Γ_{F} (U) ∩ Ū_{i} has less than 2^{−i+1}γ_{0}^{i−1}C^{−i+2}d̄^{i−1} elements. Because |U| ≤ d̄^{ℓ−3}, we may apply (12) to yield

e_{F} (U, W) ≤ C|W | < \frac{γ_{0}d̄}{2}|U|.

Because d̄ = p̄|U_{i}| for i ≤ ℓ − 2 this is a contradiction to (22), and hence the claim is proven.

Finally, using the fact that p̄|U_{ℓ−1}| ≥ p̄δm = δd̄, the same expansion argument implies that for any y ∈ Ū_{1} we have

|Γ̇_{F}^{(ℓ−2)}(y) ∩ Ū_{ℓ−1}| ≥ 2^{−ℓ+2} \frac{γ_{0}^{ℓ−2}}{C^{ℓ−3}} δd̄^{ℓ−2}.  (23)

We have thus shown that any y ∈ Ū_{1} is such that (16) holds. Since by (21) we have |Ū_{1}| ≥ (1 − δ)|U_{1}|, the proof of the lemma is finished. □

2.4 Proof of Theorem 2

Proof of Theorem 2. Let ℓ and H be as in the statement of the theorem. We shall start by defining some constants. Let first k_{0} and c be the constants from Lemma 12 applied to the triple (C^{ℓ}, H, K^{2}). Set C = 2ℓe(H), D = 3e(H),

γ_{0} = min{1, c2^{−h−1}/e(H)},  (24)
α = min{1, γ_{0}/(ℓ + 2)},  (25)

where h = |H| as usual. Apply Lemma 17 to the set of constants ℓ, α, γ_{0}, C and D to obtain the constants ε, B̄_{0}, and m_{0} whose existence is guaranteed by that lemma. Clearly, we may and shall assume that ε ≤ min{1/2, 2c}. Finally, let K_{0} = K_{0}(ε, k_{0}, D) and η = η(ε, k_{0}, D) be the constants from Lemma 10 and set

B = B_{ℓ,H} = B = |Aut(H)|K_{0}B̄_{0}.  (26)

In the remaining of the proof, we shall show that this choice of B = B_{ℓ,H} will do. Recall that we consider p = p(n) = Bn^{−β}, where β is as given by (2). In the sequel we shall also use p_{0} and (6).

As before, let H̃ = H̃(G) be the spanning subgraph of G with edge set E(H̃) = ⋃_{1≤i≤T} E(H_{i}), where H_{1}, …, H_{T} are the isolated copies of H in G. Let us now define G = G^{n} to be the family of graphs G of order n satisfying properties (a)–(c) below.

(a) H̃(G) is (η, D, p_{0})-upper-uniform.

(b) If W = (W_{i})_{i=1}^{h} is a vector of pairwise disjoint subsets of vertices of G with |W_{i}| ≥ n/ log n for all 1 ≤ i ≤ h, then Y_{W} = Y_{W}(G) ≥ (1/2)|W_{1}| … |W_{h}|p^{e(H)}, where Y_{W} is as defined in Section 2.2.3.

(c) For any vector V = (V_{i})_{i=1}^{ℓ} of pairwise disjoint m-subsets of vertices of G, where n/2K_{0} ≤ m ≤ n/k_{0}, if a V-graph F (cf. Section 2.3) with E(F) ⊏ E(H̃(G)) is such that all pairs (V_{i−1}, V_{i}) with 1 ≤ i ≤ ℓ are (ε, F, p_{0})-regular and satisfy d_{F,p_{0}}(V_{i−1}, V_{i}) ≥ γ_{0}, then F contains a copy of C^{ℓ}.

The proof of Theorem 2 will be finished if we establish the following two claims.

Claim 2 Almost every G_{p} belongs to G.

Claim 3 Every member G of G satisfies G → (C^{ℓ}, H) provided n is large enough.

Proof of Claim 2. Lemma 14 implies that almost every G = G_{p} satisfies condition (a) above, whereas Lemma 16 implies that almost every G = G_{p} satisfies (b). To prove that (c) is almost surely true for G = G_{p}, we first want to argue that any F as in the statement of (c) is an element of F_{m}(ε, B̄, γ_{0}, C, D; V, T̄), where T̄ = e(F) and B̄ = B̄_{m} > 0 is such that p_{0} = B̄m^{−1+1/(ℓ−1)}. Note that by the choices of our constants we have B̄ = p_{0}m^{1−1/(ℓ−1)} ≥ e(H)B^{e(H)}/(|Aut(H)|K_{0}) ≥ B̄_{0} (cf. (26)). Conditions (i) and (ii) in the definition of F are clearly satisfied. Condition (iii) follows from the upper uniformity of H̃ (cf. (a)) and from the assumption on the density of the pairs (V_{i−1}, V_{i}). Finally, condition (iv) in the definition of F follows from Lemma 15. Now if any such F does not contain a copy of C^{ℓ} then this implies that H̃ contains an element of F′_{m}(ε, B̄, γ_{0}, C, D; V, T̄) for some choice of m, T̄, and V. The probability of this event is by Lemmas 13 and 17 at most

|F′_{m}(ε, B̄, γ_{0}, C, D; V, T̄)|p_{0}T̄ ≤ αT̄\binom{(ℓ + 2)m^{2}}{T̄}p_{0}T̄

≤ (α\frac{e(ℓ + 2)m^{2}}{γ_{0}ℓp_{0}m^{2}} p_{0})T̄ ≤ (\frac{e}{ℓ})T̄ .  (27)

Summing (27) over all possible choices of m, T̄, and V gives us an additional factor of at most n^{3}2^{ℓn}. Using the fact that T̄ is superlinear in n, we deduce by Markov’s inequality that (c) holds for almost every G_{p}. This finishes the proof of Claim 2.

Proof of Claim 3. Let G ∈ G be fixed, and suppose G is given a blue-red edge-colouring that contains no red H. Our aim is to show that then there is a blue copy of C^{ℓ} in our graph G. Recall that G contains T isolated copies H_{1}, …, H_{T} of H. Clearly, we may pick one blue edge e_{i} ∈ E(H_{i}) for each 1 ≤ i ≤ T. We shall prove that, however we choose these T blue edges e_{i}, we shall necessarily select the edges of a C^{ℓ} ⊆ G.

We start by letting J be the spanning subgraph of G with edge set E(J) = {e_{i}: 1 ≤ i ≤ T }. From property (a) above, we know that H̃ is (η, D, p_{0})-upper-uniform, and hence so is J. We may thus apply Lemma 10 to J and obtain an (ε, k)-equitable (ε, J, p_{0})-regular partition Π = (V_{i})_{i=0}^{k} of V (J) with k_{0} ≤ k ≤ K_{0}. Write m for the cardinality of the V_{i} (1 ≤ i ≤ k).

We now consider a complete graph K^{k} on the vertex set [k], and consider the 3-edge-colouring defined as follows: colour the edge ij with colour 3 if the pair (V_{i}, V_{j}) is not (ε, J, p_{0})-regular; otherwise, colour the edge ij colour 1 if γ_{ij} = d_{J,p_{0}}(V_{i}, V_{j}) ≥ γ_{0}, and colour 2 if γ_{ij} < γ_{0}. We then apply Lemma 12 for the triple (C^{ℓ}, H, K^{2}) to the 3-edge-coloured complete graph K^{k}. For later convenience, for all i ≠ j (i, j ∈ [k]), let us colour the edges of G that join the classes V_{i} and V_{j} with the colour used to colour the edge ij ∈ E(K^{k}). Note that we now have two colours associated to each edge of G.

Suppose first that there is a monochromatic copy of C^{ℓ} of colour 1 in our K^{k}. Let V = (V_{1}, …, V_{ℓ}) be the ℓ vertex classes corresponding to this copy of C^{ℓ} and let F be the V-graph on ⋃_{i=1}^{ℓ} V_{i} containing the J-edges between consecutive classes. By property (c) we have that F contains a C^{ℓ}, and we are home.

We now observe that our K^{k} must contain fewer than ε\binom{k}{2} ≤ 2c\binom{k}{2} < ck^{2} edges coloured with colour 3, since the partition Π is (ε, J, p_{0})-regular. Therefore, we know by Lemma 12 that we may find at least ck^{h} monochromatic copies of H of colour 2 in our K^{k}. We shall see in the sequel that this leads us to a contradiction, and the proof of Claim 3 will be finished.

Observe first that m ≥ n/2k ≥ n/ log n if n is large enough. In what follows, we may and shall assume that m ≥ n/ log n. Therefore we may deduce from property (b) above that each H-subgraph of K^{k} of colour 2 determines at least m^{h}p^{e(H)}/2 isolated copies of H in G. Clearly, distinct copies of H in K^{k} determine distinct isolated copies of H in G. We may thus conclude that G contains at least

\frac{1}{2}ck^{h}m^{h}p^{e(H)} ≥ \frac{1}{2}ck^{h} (\frac{n}{2k} )^{h} p^{e(H)} ≥ c2^{−h−1}B^{e(H)}n^{1+1/(ℓ−1)}

isolated copies of H, all edges of which are coloured with colour 2. Hence the number T′ of edges of J that are coloured 2 satisfies

T′ ≥ c2^{−h−1}B^{e(H)}n^{1+1/(ℓ−1)}.  (28)

However, we also have an upper bound for T′, coming from the fact that this quantity counts only edges of G that are coloured 2. Let us write ∑_{ij}^{2} for the sum over all edges ij of K^{k} that are coloured 2. Then, by the definition of the colouring of K^{k}, by (6), and using that m ≤ n/k, we may conclude that

T′ ≤ ∑_{ij}^{2} d_{J,p_{0}}(V_{i}, V_{j})p_{0}m^{2} < \binom{k}{2}γ_{0}p_{0}m^{2} ≤ γ_{0}e(H)B^{e(H)}n^{1+1/(ℓ−1)},

which, together with the definition of γ_{0} given in (24), contradicts (28).

This finishes the proof of Claim 3, and hence the proof of Theorem 2 is complete. □

2.5 Sketch of the proof of Theorem 4

In this section we describe the alterations in the proof of Theorem 2 that yield a proof of Theorem 4. We start by defining a new class G′ of graphs to replace G from the proof of Theorem 2. In what follows, (a), (b), and (c) refer to conditions (a), (b), and (c) in the definition of the class G.

Let us write (b′) for the statement we obtain from (b) by replacing the constant 1/2 in (b) by 1/3. Moreover, to stress the length of the cycle that is involved in statement (c), let us write (c_{ℓ}) for that condition.

The n-vertex graphs that we put in the new class G′ are the ones that satisfy (a), (b′) and (c_{ℓ_{2}}) ∧ ⋯ ∧ (c_{ℓ_{r}}). We now consider the following two claims.

Claim 4 There is a constant κ > 0 such that almost every G_{p} has the property that, however we delete ≤ κn^{1+1/(ℓ_{2}−1)}/(log n)^{|H|} edges from G_{p}, we obtain a subgraph G′ of G_{p} that belongs to G′.

Claim 5 Every member G′ of G′ satisfies G′ → (H, C^{ℓ_{2}}, …, C^{ℓ_{r}}) provided n is large enough.

Proof of Claim 4. (Sketch) Condition (a) holds for any subgraph of G_{p} almost surely. Condition (b′) may be made to hold almost surely by choosing κ > 0 sufficiently small. We now consider condition (c_{ℓ_{2}}) ∧ ⋯ ∧ (c_{ℓ_{r}}). Let q ≥ ℓ_{2} be be a fixed integer. We argue that (c_{q}) holds for every subgraph G′ of G_{p} as in the statement of our claim almost surely. Let p′ = p′(n) = B_{q}n^{−β_{q}}, where B_{q} = B_{q,H} is as given in (26) and β_{q} = β(C^{q}, H). We already know that (c_{q}) holds for almost every G_{p′}. Notice that, since we are now talking about a random graph of different edge-probability, the value of p_{0} in (c_{q}) is different from the value of p_{0} in (c_{ℓ}).

Suppose for a contradiction that (c_{q}) does not hold almost surely for every subgraph G′ of G_{p} as specified. We may generate the random graph G_{p′} by first generating G_{p}, and then randomly deleting edges from G_{p} with probability 1 − p′/p. It is then easy to check that our hypothesis on (c_{q}) failing for G_{p} implies that (c_{q}) does not hold almost surely for G_{p′}, which is a contradiction. The interested reader may find the missing details in the proof of a closely related statement proved in [9] (see Lemma 19 in [9]). □

Proof of Claim 5. (Sketch) Following the proof of Claim 3, we define graphs J_{i} (2 ≤ i ≤ r) in a similar way: each isolated copy of H in G_{p} contains an edge of colour i for some 2 ≤ i ≤ r. Use these edges to define the graphs J_{i}. Now apply Lemma 10 simultaneously to all the J_{i} to obtain a partition (V_{j})_{j=0}^{k} of V (G_{p}) that is ε-regular with respect to all the J_{i} (2 ≤ i ≤ r).

We now encode the regularity/non-regularity and density of the pairs (V_{a}, V_{b}) with respect to J_{i} in an edge-coloured complete graph K^{k}. If a pair (V_{a}, V_{b}) is not ε-regular with respect to some J_{i}, we colour the edge ab of K^{k} colour r + 1 right away. Otherwise, if (V_{a}, V_{b}) is a ‘dense’ pair with respect to J_{i}, for some 2 ≤ i ≤ r, we colour ab ∈ E(K^{k}) colour i. The remaining edges we colour with colour 1. We then apply Lemma 12 to the (r + 1)-tuple of graphs (H, C^{ℓ_{2}}, …, C^{ℓ_{r}}, K^{2}).

As in the proof of Theorem 2, if we find in our edge-coloured K^{k} a monochromatic cycle C^{ℓ_{i}} of colour i, for some 2 ≤ i ≤ r, then we are done by invoking statement (c_{ℓ_{i}}). The possibility that we shall find many edges of K^{k} coloured with colour r + 1 is ruled by the ε-regularity of our partition (V_{j})_{j=0}^{k} (here we need that ε is small enough). Finally, the possibility that we shall find many monochromatic copies of H of colour 1 may be ruled out as in the proof of Claim 3 (here we need that γ_{0} should be small enough). We omit the details. □

Theorem 4 is immediate from Claims 4 and 5.

3 Proof of the 0-statement

Proof of Theorem 3. Since the case ℓ = k is contained in Theorem 1, we assume in the sequel that ℓ > k. Similarly to [10] and [13], given a graph G, we define a hypergraph G = G(G) whose hyperedges correspond to the ℓ- and k-cycles of G. Let

E_{1} = E_{1}(G) = {E(C): C is an ℓ-cycle in G},
E_{2} = E_{2}(G) = {E(C): C is a k-cycle in G}.

We put G = G(G) = E_{1} ∪ E_{2}. We refer to the hyperedges in E_{i} as hyperedges of type i (i ∈ {1, 2}).

If H is a subhypergraph of G = G(G), that is, if H ⊆ G, then we define the underlying graph G(H) of H to be the subgraph of G spanned by ⋃ H. In other words, G(H) = G[⋃ H]. Moreover, if E ∈ G, then we write V (E) for V (G(E)), the set of vertices of G incident to the edges in E. We now notice that G → (C^{ℓ}, C^{k}) simply means that

(*) for every colouring of the hypervertices of G with two colours, blue and red, say, there is either a blue hyperedge of type 1 or a red hyperedge of type 2.

A subhypergraph G_{0} ⊆ G of G is said to be critical with respect to property (*) if G_{0} fulfils (*) but if we remove any hyperedge of any type from G_{0} then the resulting hypergraph fails to have (*). The following very simple but useful claim is similar to Claim 1 in the proof of Theorem 2(a) in [10].

Claim 6 If G_{0} is critical with respect to (*) then for any hyperedge E of type i (i ∈ {1, 2}) and any hypervertex e ∈ E there exists a hyperedge F of type 3 − i such that E ∩ F = {e}.

We now need to define some constants. Set

α = k − 2 − β(k − 1) = \frac{k − ℓ}{k(ℓ − 1)}.  (29)

Observe that

−1 < α < 0.  (30)

Furthermore, let

δ = min \{−α, \frac{1}{ℓ − 1}, 1 − β\} ,  (31)

and notice that then 0 < δ < 1 + α. Indeed, the first inequality follows from the definition of β and (30), and the second follows from 1 − β < 1 + α.

Now assume that G is a graph and that G_{0} ⊆ G(G) is critical with respect to (*). As in [10], we will use Claim 6 in order to look for a subhypergraph H of G_{0} whose underlying graph G(H) is dense.

We shall give a procedure, Procedure Hypertree, that will build a subhypergraph of G_{0} that may contain some hypercycles, but will generally have a ‘hypertree structure’. Any hypergraph that may be produced by this procedure will be said to be an alternating hypertree. The key observation concerning hypertrees is that the number of those alternating hypertrees whose underlying graph is not dense is small.

Let us now describe Procedure Hypertree.

Procedure Hypertree Input: a hypergraph G_{0} = E_{1} ∪ E_{2} critical with respect to (*) Output: a triple (m, H_{m}, I_{m}) where H_{m} = {E_{0}, …, E_{m}} ⊆ G_{0}

and I_{m} ⊆ [m] × {1, 2}

⟨main body⟩

Thus, the input to Procedure Hypertree is a subhypergraph G_{0} of G(G), for some graph G, with G_{0} critical with respect to (*). Its output is a triple (m, H_{m}, I_{m}), where m is an integer, H_{m} = {E_{0}, …, E_{m}} is a subhypergraph of G_{0}, and I_{m} ⊆ [m] × {1, 2} is a certain set indicating the degeneracies present in H_{m}. Loosely speaking, the set I_{m} says how far H_{m} is from being a ‘genuine’ hypertree.

Below we shall show that (†) either the set I_{m} is large and hence the underlying graph of H_{m} is dense, or else I_{m} is small and the number of alternating hypertrees with such a small set of degeneracies is small. As an illustration, we mention that if H_{m} has no degeneracies at all, then H_{m} is uniquely determined up to isomorphism, as is the underlying graph G(H_{m}) of H_{m}, regardless of the input hypergraph G_{0}. Assertion (†) above will imply that G_{p}, with p = p(n) = bn^{−β} and sufficiently small b, almost surely does not contain a copy of the underlying graph of any alternating hypertree. This assertion will establish Theorem 3.

The main body of Procedure Hypertree is given in Figure 1.

⟨main body⟩ ≡ begin i := 0; pick E_{0} ∈ E_{2} arbitrarily; H_{0} := {E_{0}};

(1) rank and direct the edges in E_{0}; I_{0} := ∅; A_{0} := ∅; repeat ⟨extend current hypertree⟩ until |G(H_{i})| − βe(G(H_{i})) ≤ −1/500 or i ≥ log n

end

Figure 1: Main body of Procedure Hypertree

Thus, Procedure Hypertree starts by setting up a hypergraph H_{0} = {E_{0}} containing a single hyperedge that corresponds to a k-cycle of G, and then goes into an iterative process. Before we go on to detail this iterative procedure, we need to explain what is meant in line (1) in ⟨main body⟩. The hypervertices of the hypertree will be ranked with ranks starting from 1. Every time we add a new hypervertex to our hypertree, it gets a rank that is by one larger than that of its predecessor. As the hyperedges correspond to cycles in G, we can first direct the edges of a new hyperedge in a cyclic order and then rank the edges following the same order. For simplicity, we shall not make this directing and ranking procedure explict.

We now turn to the iterative procedure. This process will create sequences H_{0} ⊆ H_{1} ⊆ ⋯ and I_{0} ⊆ I_{1} ⊆ ⋯ that will eventually produce the desired output (m, H_{m}, I_{m}). For all 0 ≤ i ≤ m, we shall have H_{i} = {E_{0}, …, E_{i}} and I_{i} ⊆ [i]×{1, 2}. In the ith iteration we add the hyperedge E_{i} to H_{i−1} and we may add one of the pairs (i, 1) or (i, 2) to I_{i−1}. The latter addition to the set of degeneracies happens if E_{i} intersects H_{i−1} ‘substantially’. The procedure will also need to construct a sequence A_{0}, A_{1}, … of sets of edges, with A_{i} ⊆ ⋃ H_{i} for all 0 ≤ i ≤ m. The edges in A_{i} are said to be the assets of H_{i}.

The general iterative step is as follows.

⟨extend current hypertree⟩ ≡

if there is F ∈ E_{2} such that F ⊈ ⋃ H_{i} and |V (F) ∩ V (G(H_{i}))| ≥ 2 then ⟨add F to H_{i}⟩ else ⟨look for and add a type 1 hyperedge to H_{i}⟩

When we try to extend our current hypertree H_{i}, if it so happens that there is a type 2 hyperedge F ‘for free’ (that is, as specified in the if condition of ⟨extend current hypertree⟩), then we take it and add it to H_{i}. The idea here is that this addition will increase the density of the underlying graph of the current hypertree.

⟨add F to H_{i}⟩ ≡ i := i + 1; E_{i} := F; H_{i} := H_{i−1} ∪ {E_{i}}; rank and direct the edges in E_{i} \ ⋃ H_{i−1};

I_{i} := I_{i−1} ∪ {(i, 1)}; A_{i} := ∅

If such a ‘free’ type 2 hyperedge F does not exist, then we have to do some more work, which we describe in two stages:

⟨look for and add a type 1 hyperedge to H_{i}⟩ ≡ ⟨stage I ⟩; ⟨stage II ⟩

In ⟨stage I ⟩ we look for and add a type 1 hyperedge to our current hypertree H_{i}. This will, unfortunately, decrease the density of the current underlying graph. Therefore, in ⟨stage II ⟩, we try to add as many type 2 hyperedges to our hypertree as possible; these hyperedges all ‘hang’ on hypervertices that were added to the hypertree by the addition of the type 1 hyperedge. These hypervertices are the ‘assets’ that we acquired with the addition of the type 1 hyperedge. One may think of the process of adding type 2 hyperedges in ⟨stage II ⟩ as a process of turning these assets into ‘cash’ (i.e., density). See Figures 2 and 3.

⟨stage I ⟩ ≡ let f be the edge of smallest rank in ⋃ H_{i} for which there is a hyperedge E ∈ E_{1} with E ⊈ ⋃ H_{i}; {NB. The existence of the edge f above is proved in Claim 10.}

i := i + 1;

pick E_{i} ∈ E_{1} with E_{i} ⊈ ⋃ H_{i} and f ∈ E_{i};
H_{i} := H_{i−1} ∪ {E_{i}};

rank the edges in E_{i} \ ⋃ H_{i−1} following the cyclic order of E_{i} = C^{ℓ} given by the orientation of f, starting from the successor of f; suppose these edges are, in increasing order of rank, g_{1}, …, g_{a}; if |V (E_{i}) ∩ V (G(H_{i−1}))| = 2 then I_{i} := I_{i−1} else I_{i} := I_{i−1} ∪ {(i, 2)};

(1) A_{i} := {g_{1}, …, g_{a}}; {NB. |A_{i−1}| = 0 and a = |A_{i}| = ℓ − 1 if (i, 2) ∉ I_{i}}

Figure 2: Adding a type 1 hyperedge

⟨stage II ⟩ ≡ F := E_{i}; {NB. This is the ℓ-cycle we have just added}

for j := 1 to a do

if g_{j} ∈ A_{i} then begin i := i + 1; pick E_{i} ∈ E_{2} with E_{i} ∩ F = {g_{j}}; H_{i} := H_{i−1} ∪ {E_{i}}; rank and direct the edges in E_{i} \ ⋃ H_{i−1} following

the cyclic order of E_{i} = C^{k} given by the orientation of g_{j}, starting from the successor of g_{j};

if |V (E_{i}) ∩ V (G(H_{i−1}))| = 2 then begin I_{i} := I_{i−1}; A_{i} := A_{i−1} \ {g_{j}} end else begin I_{i} := I_{i−1} ∪ {(i, 2)}; ⟨compute A_{i}⟩ end

end

Figure 3: Adding as many type 2 hyperedges as possible

In ⟨stage II ⟩, the computation of A_{i} requires a little care. Roughly speaking, if a k-cycle E_{i} we add in ⟨stage II ⟩ contains a vertex w added to the underlying graph of the current hypertree by the addition of the ℓ-cycle in ⟨stage I ⟩, then we have to consider an asset g ∈ A_{i−1} incident to w no longer an asset. In this case we say that g was spoiled by E_{i}. See Figure 4.

The integer m = |H_{m}| − 1 ≤ log n returned by Procedure Hypertree is the length ⟨compute A_{i}⟩ ≡ A′_{i} := A_{i−1} \ {g_{j}};

for p := j + 1 to a do if the head w_{p} of g_{p} belongs to V (E_{i}) then A′_{i} := A′_{i} \ {g_{p}}; {NB. In this case we say that E_{i} spoiled g_{p}}

A_{i} := A′_{i}

Figure 4: Computing A_{i}

of H_{m}. Our alternating hypertree H_{m} is said to be degenerate at level i if (i, 1) or (i, 2) ∈ I_{m}.

Let f(i) = |G(H_{i})| − βe(G(H_{i})) = |G(H_{i})| − β| ⋃ H_{i}|. Then, for p = p(n) = n^{−β}, the expected number of copies of G(H_{i}) in G_{p} is O(n^{f(i)}). In the series of claims given below, we investigate the effect of the degeneracies on the behaviour of the function f.

For brevity, let a_{i} = |A_{i}| (0 ≤ i ≤ m). In the sequel, it will be important that H_{i} may have a non-zero number of assets only from the point in which we have just added a type 1 hyperedge up to the point in which we have cashed all available assets in the for loop in ⟨stage II ⟩. In other words, a_{i} > 0 can only occur between line (1) in ⟨stage I ⟩ and the end of ⟨stage II ⟩. In particular, a_{0} = a_{m} = 0.

Claim 7 For all 1 ≤ i ≤ m, if (i, 1), (i, 2) ∉ I_{i} then f(i) + αa_{i} = f(i − 1) + αa_{i−1}.

Proof. Consider first the case in which E_{i} is of type 1. Then a_{i−1} = 0 and moreover a_{i} = ℓ − 1, since (i, 2) ∉ I_{i} (cf. the remark in line (1) of ⟨stage I ⟩). Therefore E_{i} contributes exactly ℓ − 2 new vertices and exaclty ℓ − 1 new edges to H_{i−1}. Hence,

f(i) + αa_{i} = f(i − 1) + ℓ − 2 − β(ℓ − 1) + (k − 2 − β(k − 1))(ℓ − 1)
= f(i − 1) + (k − 1)(ℓ − 1) − 1 − βk(ℓ − 1)
= f(i − 1) + αa_{i−1}.

If E_{i} is of type 2 then a_{i} = a_{i−1} − 1 and

f(i) + αa_{i} = f(i − 1) + (k − 2) − β(k − 1) + α(a_{i−1} − 1)
= f(i − 1) + αa_{i−1},

as required.

Claim 8 For all 1 ≤ i ≤ m, if (i, 1) ∈ I_{i} then f(i) + αa_{i} ≤ f(i − 1) + αa_{i−1} − δ.

Proof. Let H ⊆ C^{k} be the graph with vertex set V (E_{i}) ∩ V (G(H_{i−1})) and edge set E_{i} ∩ ⋃ H_{i−1}, that is, H is the intersection of (V (E_{i}), E_{i}) and G(H_{i−1}). Clearly, H is a disjoint union of paths. Moreover, G(H_{i}) has k − |H| new vertices and k − e(H) new edges. Therefore, by |H| ≥ e(H) + 1, |H| ≥ 2, and β ≤ 1, and by the definitions of α and δ (cf. (29) and (31)), we have

f(i) = f(i − 1) + k − |H| − β(k − e(H))
≤ f(i − 1) + k − 2 − β(k − 1)
≤ f(i − 1) − δ,

which implies the claim, since a_{i−1} = a_{i} = 0.

Claim 9 For all 1 ≤ i ≤ m, if (i, 2) ∈ I_{i} then f(i) + αa_{i} ≤ f(i − 1) + αa_{i−1} − δ.

Proof. Consider first the case in which E_{i} is of type 1. Let H ⊆ C^{ℓ} be the intersection of the two graphs (V (E_{i}), E_{i}) and G(H_{i−1}). Then a_{i} = ℓ − e(H) and

f(i) + αa_{i} = f(i − 1) + ℓ − |H| − β(ℓ − e(H)) + α(ℓ − e(H))
= f(i − 1) + (ℓ − e(H))(k − 1 − kβ) + e(H) − |H|
= f(i − 1) + \frac{ℓ − e(H)}{ℓ − 1} + e(H) − |H|.  (32)

If e(H) ≥ 2 then we conclude from |H| ≥ e(H) + 1 that (ℓ − e(H))/(ℓ − 1) + e(H) − |H| ≤ −1/(ℓ − 1) ≤ −δ (cf. (31)). If e(H) = 1 then |H| ≥ 3 and thus (ℓ − e(H))/(ℓ − 1) + e(H) − |H| ≤ −δ. Because of a_{i−1} = 0 we have that (32) is in both cases at most f(i − 1) + αa_{i−1} − δ.

Let now E_{i} be of type 2 and let H ⊆ C^{k} be the intersection of the two graphs (V (E_{i}), E_{i}) and G(H_{i−1}). We first deduce from the fact that g_{j} is an asset before we add E_{i}, that is, g_{j} ∈ A_{i−1}, that H ≠ C^{k}. Indeed, let E_{i′} be the hyperedge of type 1 that E_{i} is attached to; i.e., E_{i} ∩ E_{i′} = {g_{j}}. Because of the if condition in ⟨extend current hypertree⟩, the hyperedge E_{i} is disjoint from ⋃ H_{i′−1}. Let w be the head of g_{j}. Then if E_{i} ⊆ ⋃ H_{i−1}, the vertex w must be incident to some edge in ⋃ H_{i−1} \ ⋃ H_{i′}. This means that g_{j} was spoiled before, i.e., g_{j} ∉ A_{i−1}, which is a contradiction. Hence H ≠ C^{k}.

Let b be such that a_{i} = a_{i−1} − b. Observe that b ≥ 1. If E_{i} spoils an edge g_{h} then the head w_{h} of g_{h} is isolated in H. Indeed, E_{i} contains no edge from ⋃ H_{i′−1}, no edge from E_{i′} incident to w_{h}, and, since g_{h} has not been spoiled before, w_{h} is incident to no edge in ⋃ H_{i−1} \ ⋃ H_{i′}. Therefore, there does not exist any edge in E_{i} ∩ ⋃ H_{i−1} incident to w_{h}. Hence w_{h} is indeed isolated in H. Setting J := H \ {w_{f}: g_{f} is spoiled by E_{i}} we get that |H| = |J| + b − 1. Moreover,

f(i) + αa_{i}
= f(i − 1) + k − |J| − (b − 1) − β(k − e(J)) + α(a_{i−1} − b)
= f(i − 1) + αa_{i−1} − (b − 1)(α + 1) + k − |J| − β(k − e(J)) − α
≤ f(i − 1) + αa_{i−1} − (b − 1)(α + 1) + (e(J) − |J| + 1) + (e(J) − 1)(β − 1).

The three last terms are non-positive. If b ≥ 2 then the first term is smaller than −δ because of δ < 1 + α. If b = 1 then J is a proper subgraph of E_{i} = C^{k} with J ≠ K^{2} and therefore either e(J) > 1 or |J| > e(J) + 1 = 2 implying that one of the two last terms is smaller or equal than −δ, and the claim is proven.

Claim 10 The edge f as specified in ⟨stage I ⟩ always exists.

Proof. Assume that Procedure Hypertree gets stuck at the beginning of ⟨stage I ⟩ at iteration i because the edge f as specified does not exist. Our aim is to reach a contradiction.

Let G_{i} = G(H_{i}) be the underlying graph of H_{i}, so that G_{i} is spanned by its edge set E(G_{i}) = ⋃ H_{i}. We start with the following assertion.

(**) For both q ∈ {1, 2}, if e ∈ E ⊆ E(G_{i}) and E ∈ E_{q}, then there exists a hyperedge F ∈ E_{3−q} such that e ∈ F ⊆ E(G_{i}) and moreover E ∩ F = {e}.

Let us prove assertion (**). Suppose first that q = 1. Then Claim 6 gives a hyperedge F ∈ E_{2} with E ∩ F = {e}. The if condition in ⟨extend current hypertree⟩ implies that F ⊆ ⋃ H_{i} = E(G_{i}), as required. If q = 2, then Claim 6 gives F ∈ E_{1} with E ∩ F = {e}. Since we did not find an edge f as specified on the first line of ⟨stage I ⟩, we must have F ⊆ ⋃ H_{i} = E(G_{i}). Assertion (**) is proved.

An immediate corollary to (**) is the following assertion.

(‡) Every edge e of G_{i} is contained in an ℓ-cycle C_{1} and in a k-cycle C_{2} with E(C_{q}) ∈ E_{q} (q ∈ {1, 2}) and E(C_{1}) ∩ E(C_{2}) = {e}.

In particular, we have the following observation.

(i) The minimal degree of G_{i} is at least 3.

Let us now consider the simpler case in which k ≥ 4. Because of ℓ > k, it is easily seen that β(C^{ℓ}, C^{k}) ≥ β(C^{5}, C^{4}) = 11/16. On the other hand, by (i), we have e(G_{i}) ≥ (3/2)|G_{i}| and therefore in this case we have

f(i) = |G_{i}| − βe(G_{i}) ≤ |G_{i}| (1 − \frac{3}{2} × \frac{11}{16}) ≤ −\frac{1}{500}.

We have thus reached a contradiction, since this implies that Procedure Hypertree should have stopped with m = i.

We now turn to the case k = 3. We shall have to argue more carefully here. We introduce some notation in order to avoid repetition. Suppose x_{1}, x_{2}, and x_{3} are three vertices of G_{i}. We shall write T (x_{1}, x_{2}, x_{3}) when these vertices induce a triangle in G_{i} and moreover {x_{1}x_{2}, x_{2}x_{3}, x_{1}x_{3}} ∈ E_{2}. Similarly, if x_{1}, …, x_{ℓ} define, in this order, an ℓ-cycle C^{ℓ} of G_{i} and furthermore E(C^{ℓ}) ∈ E_{1}, then we shall write C(x_{1}, …, x_{ℓ}).

Let A(x_{1}x_{2}, T (x_{1}, x_{2}, x_{3})) stand for the application of (**) to the edge x_{1}x_{2} and the type 2 hyperedge corresponding to {x_{1}, x_{2}, x_{3}}. Thus A(x_{1}x_{2}, T (x_{1}, x_{2}, x_{3})) gives us the existence of vertices y_{3}, …, y_{ℓ} ∈ V (G_{i}) \ {x_{1}, x_{2}} with y_{3} ≠ x_{3} ≠ y_{ℓ} and such that C(x_{1}, x_{2}, y_{3}, …, y_{ℓ}). Similarly, let A(x_{1}x_{2}, C(x_{1}, …, x_{ℓ})) stand for the corresponding statement guaranteeing the existence of a vertex y_{3} ∈ V (G_{i}) \ {x_{1}, x_{2}, x_{3}, x_{ℓ}} with T (x_{1}, x_{2}, y_{3}). Now we prove in a couple of steps that G_{i} has large density. (ii) A vertex of degree 3 in G_{i} is only adjacent to vertices of degree at least 4. To prove the assertion above, assume that there are two vertices of degree 3, say, x and y, that are adjacent in G_{i}. By (‡), we have a vertex z such that T (x, y, z). We now argue as follows.

(a) A(xy, T (x, y, z)) gives 2 distinct vertices v and w ∉ {x, y, z} with C(v, x, y, w, …).

(b) A(yz, T (x, y, z)) gives C(w, y, z, …), since d(y) = 3.

(c) A(wy, C(w, y, z, …)) gives T (w, y, x), since d(x) = d(y) = 3.

However, T (w, y, x) implies that v = w, which is a contradiction. Assertion (ii) is proved.

(iii) Every vertex of G_{i} has a neighbour of degree at least 4. Indeed, let x be a vertex of G_{i}, and let y be a neighbour of x. Then, by (‡), there exists a vertex z with T (x, y, z). By (ii), either y or z has degree at least 4, and (iii) is proven.

Consider first the case ℓ ≥ 5. Denote by a and b the number of vertices of degree exactly 3 and at least 4 in G_{i}, respectively. Assertions (ii) and (iii) imply that ∑_{d(v)≥4} d(v) ≥ 3a + b. Therefore

\frac{2e(G_{i})}{|G_{i}|} ≥ max \{\frac{3a + 4b}{a + b}, \frac{6a + b}{a + b}\} ≥ min_{x≥0} max\{4 − x, 1 + 5x\} = \frac{7}{2}.

Using β(C^{ℓ}, C^{3}) ≥ β(C^{5}, C^{3}) = 7/12 we have that

f(i) = |G_{i}| − βe(G_{i}) ≤ |G_{i}| (1 − \frac{7}{12} × \frac{7}{4}) ≤ −\frac{1}{500}.

In the sequel we assume that ℓ = 4.

(iv) Every vertex of degree 3 in G_{i} has a neighbour of degree at least 5. Assume to the contrary that there is a vertex v ∈ V (G_{i}) of degree 3 with neighbours x, y, and z all having degree 4. Recalling (‡), we may assume without loss of generality that T (v, x, y) and T (v, y, z). Now we argue as follows.

(a) Since d(v) = 3, we have that A(vy, T (v, y, z)) gives a vertex w ∈ V (G_{i}) \ {v, x, y, z} such that C(w, x, v, y).

(b) A(vy, T (v, x, y)) similarly gives a vertex w′ ∈ V (G_{i})\{v, x, y, z} such that C(w′, z, v, y). However, d(y) = 4, and hence w = w′.

(c) Since d(v) = 3, we have that A(vz, C(w, y, v, z)) gives that T (v, z, x).

(d) A(yz, T (v, y, z)) gives either C(y, z, x, w) or else C(y, z, w, x).

We reach a contradiction analysing the two possibilities in (d) separately. If C(y, z, x, w), consider A(xw, C(y, z, x, w)) to get T (x, w, v). But then vw ∈ E(G_{i}), contradicting d(v)=3. On the other hand, if C(y, z, w, x), consider A(xw, C(x, y, z, w)) to deduce T (x, w, v) again. Therefore assertion (iv) is proved.

We now estimate the density of G_{i} from below. Let a and b denote the number of vertices of degree 3 and 4 in G_{i}, respectively, and let c be the number of vertices of degree at least 5. By (ii) and (iii) we have that ∑_{d(v)≥4} d(v) ≥ 3a + b + c. Assertions (iii) and (iv) imply that ∑_{d(v)≥5} d(v) ≥ a + c. Therefore we have

\frac{2e(G_{i})}{|G_{i}|} ≥ max \{\frac{3a + 4b + 5c}{a + b + c}, \frac{6a + b + c}{a + b + c}, \frac{4a + 4b + c}{a + b + c}\} .

Setting x = a/(a + b + c) and y = c/(a + b + c), this implies

\frac{2e(G_{i})}{|G_{i}|} ≥ min_{x,y≥0} max\{4 − x + y, 1 + 5x, 4 − 3y\} = \frac{83}{23},

as one may easily check. Furthermore β(C^{4}, C^{3}) = 5/9. Thus

f(i) = |G_{i}| − βe(G_{i}) ≤ |G_{i}| (1 − \frac{83}{46} × \frac{5}{9}) ≤ −\frac{1}{500},

and Claim 10 is proven.

Claim 11 Let (m, H_{m}, I_{m}) be the output of Procedure Hypertree. Then the following assertions hold:

(a) f(m) ≤ f(0) = 1 + 1/(ℓ − 1) ≤ 3/2, m ≤ log n + ℓ, and

|I_{m}| ≤ M := ℓ + ⌈\frac{f(0) + 1/500}{δ}⌉ − 1.  (33)

(b) Either (i) m ≥ log n or else (ii) f(m) ≤ −1/500.

Proof. (a) The inequality for f(m) follows easily from Claims 7, 8, and 9, and the fact that a_{0} = a_{m} = 0. Suppose now that m ≥ log n. Then, letting i be the largest integer strictly smaller than log n, we see that m ≤ i + ℓ < log n + ℓ, as required. To see (33), suppose for a contradiction that |I_{m}| ≥ M + 1. This time let i be the maximal integer not greater than m for which a_{i} = 0. Then m ≤ i + ℓ, and hence |I_{i}| = |I_{m} ∩ ([i] × {1, 2})| ≥ M +1−ℓ ≥ ⌈(f(0)+1/500)/δ⌉. Observing that a_{0} = a_{m} = 0, we have, applying Claims 7, 8, and 9, that

f(i) ≤ f(0) − δ ⌈\frac{f(0) + 1/500}{δ}⌉ ≤ −\frac{1}{500}.

However, this shows that Procedure Hypertree should have stopped after the ith iteration (see Figure 1), which is a contradiction.

Assertion (b) follows trivially from the until condition in ⟨main body⟩. This finishes the proof of Claim 11.

The heart of the proof of Theorem 3 is Claim 13 below. Loosely speaking, the idea is as follows. If G_{p} → (C^{ℓ}, C^{k}), then G(G_{p}) contains a subhypergraph G_{0} critical with respect to (*). We may then feed this hypergraph G_{0} into Procedure Hypertree, and obtain a hypertree H_{m} ⊆ G_{0} satisfying the conditions given in Claim 11. Using these conditions, we show in Claim 13 that a.e. G_{p} does not contain the underlying graph G(H_{m}) of H_{m} if p = p(n) = bn^{−β} and b is small enough. However, this is a contradiction, since clearly G(H_{m}) ⊆ G_{p}. We shall have thus proved Theorem 3.

To detail the argument sketched above, we need to introduce some definitions. Fix a graph G on n vertices such that G → (C^{ℓ}, C^{k}). Consider all possible choices for G_{0} ⊆ G(G), the (*)-critical subhypergraph of G(G). Recall that Procedure Hypertree is a nondeterministic procedure, and, for each G_{0} as above, consider all sequences H_{0} ⊆ H_{1} ⊆ ⋯ that may be generated by Procedure Hypertree. Now, for each i ≥ 0, let F(i) be the set of all hypergraphs H_{i} that may be obtained in the process described above, letting the graph G vary over all graphs G′ with vertex set [n] and satisfying G′ → (C^{ℓ}, C^{k}).

For each i ≥ 0, let G(i) be the family of all graphs, up to isomorphism, that are underlying graphs of the hypergraphs H_{i} in F(i). Now recall that each H_{i} ∈ F(i) has an associated set of degeneracies I_{i} = I_{i}(H_{i}) ⊆ [i] × {1, 2}. For all 0 ≤ j ≤ i, let G(i, j) be the collection of all graphs G ∈ G(i) that are underlying graphs of hypergraphs H_{i} ∈ F(i) with j degeneracies, that is, with |I_{i}(H_{i})| = j. Finally, let G_{≤}(m, d) = ⋃ G(i, j), where the union is taken over all 0 ≤ i ≤ m and 0 ≤ j ≤ d.

The crucial lemma in the proof of Claim 13 is as follows.

Claim 12 (i) For all 0 ≤ j ≤ i, we have |G(i, j)| ≤ i^{j}(iℓ)^{jℓ}.

(ii) For all m ≥ 1 and 0 ≤ d ≤ m, we have |G_{≤}(m, d)| ≤ (m + 1)m^{d+1}(mℓ)^{ℓ(d+1)}.

Proof. (i) For a hypergraph H_{i} in F(i), let J_{i}(H_{i}) ⊆ [i] be the set of integers j for which H_{i} is degenerate at level j. In other words, j ∈ J_{i}(H_{i}) if and only if one of (j, 1), (j, 2) belongs to I_{i}(H_{i}). For a set J ⊆ [i], let G(i, J) be the set of all graphs G ∈ G(i, |J|) that are underlying graphs of H_{i} ∈ F(i) with J_{i}(H_{i}) = J. For simplicity, put g(i, j) = |G(i, j)| and g(i, J) = |G(i, J)|.

Let us first fix J ⊆ [i] and estimate g(i, J). We claim that

g(i, J) ≤ \{ \begin{matrix}g(i − 1, J) & if i ∉ J \\ g(i − 1, J \ \{i\})(iℓ)_{ℓ} & if i ∈ J, \end{matrix}  (34)

where, as usual, (a)_{b} = a(a − 1) ⋯ (a − b + 1). Let us first suppose that i ∉ J. Let G ∈ G(i, J), and suppose that G = G(H_{i}) with J_{i}(H_{i}) = J. Since i ∉ J, the ranks of the elements of the ith hyperedge E_{i} of H_{i} are uniquely determined once H_{i−1} = H_{i} \ {E_{i}} is given. At this point it is crucial that in Procedure Hypertree, when adding a nondegenerate hyperedge to our current hypertree, we choose the hypervertex with lowest rank to ‘hang’ our new hyperedge on. A moment’s thought now shows that we have thus implicitly defined an injection G(i, J) ↪ G(i−1, J), since here we are dealing with graphs up to isomorphism.

Suppose now that i ∈ J. Let G, H_{i}, and E_{i} be as before. Then the number of ways we can choose the cycle C of G that corresponds to the hyperedge E_{i} can be bounded very generously by (iℓ)_{ℓ}. Indeed, the underlying graph G(H_{i−1}) of H_{i−1} = H_{i−1} \ {E_{i}} has at most iℓ vertices, and to define C it suffices to select its vertices from V (G(H_{i−1})). This completes the proof of (34).

By induction, we may deduce from (34) that g(i, J) ≤ {(iℓ)_{ℓ}}^{|J|}, since g(i, ∅) ≤ 1 for any i ≥ 0. Therefore

g(i, j) = |G(i, j)| = | ⋃_{J⊆[i]} G(i, J)| ≤ \binom{i}{j}\{(iℓ)_{ℓ}\}^{j} ≤ i^{j}(iℓ)^{jℓ},

completing the proof of (i). Assertion (ii) follows easily from (i), since

|G_{≤}(m, d)| ≤ ∑_{i=0}^{m} ∑_{j=0}^{d} g(i, j) ≤ ∑_{i=0}^{m} ∑_{j=0}^{d} i^{j}(iℓ)^{jℓ} ≤ ∑_{i=0}^{m}{i(iℓ)^{ℓ}}^{d+1} ≤ (m + 1)m^{d+1}(mℓ)^{ℓ(d+1)},

as required.

In the sequel, we apply Claim 12(ii) for m = O(log n) and d = O(1). Our claim tells us that, in this case, G_{≤}(m, d) has polylogarithmic size only.

Before stating our last claim, we need to introduce a piece of notation. Below, we shall write G̃_{≤}(m, d) for the family of graphs G ∈ G_{≤}(m, d) that are isomorphic to underlying graphs G(H_{m}) of outputs H_{m} of Procedure Hypertree.

Claim 13 Put p = p(n) = e^{−2}n^{−β}, m′ = ⌊log n + ℓ⌋, and let M be as in (33). Then the expected number of subgraphs of G_{p} that are isomorphic to members of G̃_{≤}(m′, M) is o(1).

Proof. An element G of G̃_{≤}(m′, M) corresponds to an output H_{m} of Procedure Hypertree, and hence the assertions in Claim 11 hold for H_{m}. In particular, we may write G̃_{≤}(m′, M) = G̃_{≤}^{(i)}(m′, M) ∪ G̃_{≤}^{(ii)}(m′, M), where the elements G in G̃_{≤}^{(i)}(m′, M) correspond to H_{m} satisfying Claim 11(b)(i), and similarly to G̃_{≤}^{(ii)}(m′, M).

We now claim that the expected number of subgraphs of G_{p} that are isomorphic to members of G̃_{≤}^{(i)}(m′, M) is o(1). Fix G ∈ G̃_{≤}^{(i)}(m′, M). Writing #{G ⊆ G_{p}} for the number of subgraphs of G_{p} isomorphic to G, we have

E(#\{G ⊆ G_{p}\}) ≤ (\frac{1}{e^{2}} )^{e(G)} n^{|G|−βe(G)} ≤ (\frac{1}{e^{2}} )^{log n} n^{f(0)} ≤ n^{−1/2}.

Our claim then follows as |G̃_{≤}^{(i)}(m′, M)| is, by Claim 12, only polylogarithmic in n.

Similarly, we claim that the expected number of subgraphs of G_{p} that are isomorphic to members of G̃_{≤}^{(ii)}(m′, M) is o(1). Indeed, for any G ∈ G̃_{≤}^{(ii)}(m′, M), we have

E(#{G ⊆ G_{p}}) ≤ n^{|G|−βe(G)} ≤ n^{−1/500},

but again |G̃_{≤}^{(ii)}(m′, M)| is only polylogarithmic in n. This finishes the proof of Claim 13.

To finish the proof of Theorem 3, it suffices to recall that, by Claim 11, the event G_{p} → (C^{ℓ}, C^{k}) implies that G_{p} contains a subgraph isomorphic to an element of G̃_{≤}(m′, M), where m′ and M are as in Claim 13. □

4 Deterministic consequences

Proof of Corollary 7. Let β = β(C^{ℓ_{2}}, H). Let B and κ be the constants from Theorem 4 for ℓ_{2}, …, ℓ_{r} and H. Let

ε = min{1 + 1/(ℓ_{2} − 1) − |F | + β(C^{ℓ_{2}}, H)e(F)},

where the minimum is taken over all graphs F ∈ V_{ℓ_{2},H,t}. Then ε > 0 and the expected number of copies of graphs from V_{ℓ_{2},H,t} in G_{p}, where p = Bn^{−β}, is O(n^{1+1/(ℓ_{2}−1)−ε}). Therefore, by Markov’s inequality, the number of copies of graphs from V_{ℓ_{2},H,t} is almost surely at most κn^{1+1/(ℓ_{2}−1)}/(log n)^{|H|}. If G_{p} is a random graph having this property and fulfilling the statement of Theorem 4 then we define a graph G by removing one edge from every copy of a graph of V_{ℓ_{2},H,t} in G_{p}. The graph G has the required properties. □

Proof of Theorem 8. We show that for any t there exists a graph on more than t vertices which is critical for (C^{ℓ_{i}})_{1≤i≤r}. Let B and β = β(C^{ℓ_{2}}, C^{ℓ_{1}}) be the constants from Corollary 5. Let T = {F: |F | ≤ t and |F | − βe(F) ≤ −1/500}. For p = Bn^{−β}, almost all graphs G_{p} do not contain any graphs from T . Furthermore G_{p} → (C^{ℓ_{1}}, …, C^{ℓ_{r}}) almost surely by Corollary 5. Therefore there exists a graph H on n ≥ t vertices with H → (C^{ℓ_{1}}, …, C^{ℓ_{r}}) and not containing any graph from T as a subgraph. Assume that there exists a subgraph K of H on t vertices such that K → (C^{ℓ_{1}}, …, C^{ℓ_{r}}). Hence in particular K → (C^{ℓ_{1}}, C^{ℓ_{2}}). Let K be the hypergraph with hyperedges being the ℓ_{1}-and ℓ_{2}- cycles of K. Let K_{0} be a critical subgraph of K with respect to property (*) from Section 3. We now run Procedure Hypertree on the input K_{0} but where we exit the repeat-loop in ⟨main body⟩ only if |G(H_{i})| − βe(G(H_{i})) ≤ −1/500 thus possibly creating hypertrees that are of length more than log t. It follows easily from the proof of the 0-statement (cf., e.g., Claim 11) that the output H_{m} is such that its underlying graph G(H_{m}) is in T , contradicting the fact that H is T -free. It follows that some subgraph of H containing more than t vertices is critical for (C^{ℓ_{i}})_{1≤i≤r}. □

References

[1] B. Bollobás. Random Graphs. Academic Press, 1985.

[2] R.L. Graham, B. Rothschild, and J.H. Spencer. Ramsey Theory. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, New York, second edition, 1990.

[3] P.E. Haxell, Y. Kohayakawa, and T. Łuczak. Turán’s extremal problem in random graphs: forbidding odd cycles. Combinatorica. To appear.

[4] P.E. Haxell, Y. Kohayakawa, and T. Łuczak. Turán’s extremal problem in random graphs: forbidding even cycles. J. Combinatorial Theory, Series B, 64:273–288, 1995.

[5] S. Janson. Poisson approximation for large deviations. Random Structures and Algorithms, 1(2):221–229, 1990.

[6] Y. Kohayakawa. The regularity lemma of Szemerédi for sparse graphs. Manuscript, 1993.

[7] Y. Kohayakawa, B. Kreuter, and A. Steger. An extremal problem for random graphs and the number of graphs with large even-girth. Submitted, 1995.

[8] Y. Kohayakawa, T. Łuczak, and V. Rödl. Arithmetic progressions of length three in subsets of a random set. Acta Arithmetica. To appear.

[9] Y. Kohayakawa, T. Łuczak, and V. Rödl. On K^{4}-free subgraphs of random graphs. Submitted, 1995.

[10] B. Kreuter. Threshold functions for asymmetric Ramsey properties with respect to vertex colorings. Submitted, 1995.

[11] T. Łuczak. On Ramsey minimal graphs. The Electronic Journal of Combinatorics, 1:R#4, 1994.

[12] T. Łuczak, A. Ruciński, and B. Voigt. Ramsey properties of random graphs. J. Combinatorial Theory, Series B, 56:55–68, 1992.

[13] V. Rödl and A. Ruciński. Lower bounds on probability thresholds for Ramsey properties. In Combinatorics—Paul Erdős is Eighty (Volume 1), Bolyai Soc. Math. Studies, pages 317–346, Budapest, 1993.

[14] V. Rödl and A. Ruciński. Random graphs with monochromatic triangles in every edge coloring. Random Structures and Algorithms, 5(2):253–270, 1994.

[15] V. Rödl and A. Ruciński. Threshold functions for Ramsey properties. J. Amer. Math. Soc., 8(4):917–942, 1995.

[16] E. Szemerédi. Regular partitions of graphs. In J.-C. Bermond, J.-C. Fournier, M. Las Vergnas, and D. Sotteau, editors, Problèmes Combinatoires et Théorie des Graphes, Proc. Colloque Inter. CNRS, pages 399–401, Paris, 1978. CNRS.