TURÁN’S EXTREMAL PROBLEM IN RANDOM

GRAPHS: FORBIDDING ODD CYCLES

P.E. Haxell, Y. Kohayakawa and T. Łuczak

Abstract. For 0 < γ ≤ 1 and graphs G and H, we write G →_{γ} H if any γproportion of the edges of G span at least one copy of H in G. As customary, we write C^{k} for a cycle of length k. We show that, for every fixed integer ℓ ≥ 1 and real η > 0, there exists a real constant C = C(ℓ, η), such that almost every random graph G_{n,p} with p = p(n) ≥ Cn^{−1+1/2ℓ} satisfies G_{n,p} →_{1/2+η} C^{2ℓ+1}. In particular, for any fixed ℓ ≥ 1 and η > 0, this result implies the existence of very sparse graphs G with G →_{1/2+η} C^{2ℓ+1}.

§0. Introduction

In this note we are interested in a Turán type problem concerning extremal subgraphs of random graphs, which may be formulated as follows. Given a graph H, we ask for the maximal size of an H-free subgraph of G_{p} = G_{n,p}, the usual binomial random graph on n vertices with edge probability p. Let us make this precise by introducing some definitions and notation.

Let a graph G be given. As customary, write |G| for the order |V (G)| of G and e(G) for the size |E(G)| of G. If H is a graph, we say that G is H-free if G does not contain a subgraph isomorphic to H. Also, we let ex(G, H) be the maximal size of an H-free subgraph of G, that is ex(G, H) = max{e(J): H ⊄ J ⊂ G}. For instance, if G = K^{n}, the complete graph on n vertices, then ex(K^{n}, H) = ex(n, H), the usual Turán number of H. Here we are concerned with the case in which G = G_{p} = G_{n,p}, the random graph on V (G_{p}) = {1, …, n} where each edge ij (1 ≤ i < j ≤ n) belongs to G_{p} with probability p, independently of all other edges. (See Bollobás [3] for details concerning random graphs.)

With the notation as above, our Turán type extremal problem for random graphs asks for the investigation of the random variable Z_{H} = Z_{H}(G_{p}) = ex(G_{p}, H) for any given 0 < p = p(n) ≤ 1.

A celebrated result of Erdős and Stone [4] (see also Bollobás [2]) states that the asymptotic behaviour of ex(n, H) = ex(K^{n}, H) is determined by the chromatic number of H, provided only that χ(H) ≥ 3. Indeed, for any H we have

lim_{n→∞} \frac{ex(K^{n}, H)}{e(K^{n})} = 1 − \frac{1}{χ(H) − 1} .

Typeset by AMS-TEX

1991 Mathematics Subject Classification. Primary 05C80, 05C35, 05C38; Secondary 05C55.

Key words and phrases. Turán’s extremal problem, cycles, random graphs, Szemerédi’s lemma.

The first author was partially supported by NSERC. The second author was partially supported by FAPESP (Proc. 93/0603–1) and by CNPq (Proc. 300334/93–1). The third author was partially supported by KBN grant 2 1087 91 01.

Now, clearly, for every family of graphs {G^{n}}_{n≥1} with each G^{n} of order n and with at least one edge, we have

lim inf_{n→∞} \frac{ex(G^{n}, H)}{e(G^{n})} ≥ 1 − \frac{1}{χ(H) − 1} .  (1)

However, if e(G^{n}) → ∞ as n → ∞ and, for all large n, the number of copies of H in G^{n} is much larger than e(G^{n}) and these copies are distributed in G^{n} in a “uniform” way, then, in fact, one may expect that equality holds in (1) with lim inf replaced by lim. We conjecture that this is indeed the case when the G^{n} are the random graphs G_{n,p} of sufficiently large density to make the expected number of copies of H in G_{n,p} larger than the expected size of G_{n,p} by a factor that tends to ∞ arbitrarily slowly. Strong evidence in support of this conjecture is provided by a recent, beautiful result of Rödl and Ruciński [16], who proved that every rcolouring of the edges of such a dense random graph G_{n,p} leads to a monochromatic copy of H almost surely, i.e. with probability tending to 1 as n → ∞ (For earlier related results see [11, 14, 15].)

The case H = K^{3} of our conjecture is already well understood. One of the results in Frankl and Rödl [5] says that ex(G_{p}, K^{3}) = (1/2 + o(1))e(G_{p}) almost surely if p = p(n) ≥ n^{−1/2+ε} and ε > 0 is any fixed constant. More recently, Babai, Simonovits, and Spencer [1] showed that if p = 1/2, then ex(G_{p}, K^{3}) is almost surely the maximal size of a bipartite subgraph of G_{p}. Moreover, it is shown in [1] that almost surely all the K^{3}-free subgraphs of G_{p} of maximal size are in fact bipartite. In this note we investigate ex(G_{p}, C^{2ℓ+1}) for ℓ ≥ 1, where as usual we write C^{2ℓ+1} for a cycle of length 2ℓ + 1. Our main result is as follows.

Theorem 1. Let an integer ℓ ≥ 1 and a real number 0 < η ≤ 1/2 be fixed. Then there is a constant C = C(ℓ, η) > 0 such that, if p = p(n) ≥ Cn^{−1+1/2ℓ}, then almost every G_{p} ∈ G(n, p) satisfies ex(G_{p}, C^{2ℓ+1}) ≤ (1/2 + η)e(G_{p}).

Clearly, by (1), we always have ex(G_{p}, C^{2ℓ+1}) ≥ 1/2. Moreover, the condition on p = p(n) in Theorem 1 cannot be substantially weakened. To see this, just note that, for p = p(n) = δn^{−1+1/2ℓ}, almost every G_{p} has O{(δ^{2ℓ}/2ℓ)e(G_{p})} copies of C^{2ℓ+1}. Thus ex(G_{p}, C^{2ℓ+1}) ≥ {1 − O(δ^{2ℓ}/ℓ)}e(G_{p}) almost surely for such p, and hence the lower bound for p in Theorem 1 is, as claimed, essentially best possible: given any 0 < ε ≤ 1, there is a δ = δ(ε) > 0 such that for p = p(n) as above we have ex(G_{p}, C^{2ℓ+1}) ≥ (1 − ε)e(G_{p}) almost surely. We mention that the general approach in the proof of Theorem 1 was inspired by Rödl and Ruciński [16] (cf. Section 2.1).

The result of Frankl and Rödl mentioned above has as a corollary a purely deterministic result that in fact settled a problem of Erdős and Nešetřil. For convenience, for any two graphs G and H and any given 0 < γ ≤ 1, let us write G →_{γ} H if ex(G, H) < γe(G). Then the deterministic result of Frankl and Rödl [5] says that, for any 0 < η ≤ 1/2, there is a K^{4}-free graph G = G_{η} such that G →_{1/2+η} K^{3}. Here, as a corollary to Theorem 1, we show that, for any 0 < η ≤ 1/2 and ℓ ≥ 1, there are ‘very sparse’ graphs G = G_{η,ℓ} satisfying G →_{1/2+η} C^{2ℓ+1}. For instance, G may be required to have girth g(G) = 2ℓ+1, and to contain no two (2ℓ+1)-cycles that share more than two vertices (cf. Corollary 11).

Finally, we mention that our conjecture above for H = C^{4} follows from Füredi [6] in a rather stronger form. The case in which H is a general even cycle C^{2ℓ} (ℓ ≥ 2) will be dealt with in [8], where a completely different approach from the one here will be used.

This note is organised as follows. In §1 we give a few preliminary definitions and lemmas. The proof of Theorem 1, which is based on a somewhat surprising deterministic lemma on subgraphs of pseudo-random graphs, Lemma 6, is the subject of §2. The statement of Lemma 6 and the proof of Theorem 1 are given in Section 2.1, and the proof of Lemma 6 is given in Section 2.2. In §3 we give the deterministic consequences of Theorem 1.

§1. Preliminary Lemmas

We start with a variant of the powerful lemma of Szemerédi [17] concerning regular partitions of graphs. Let a graph G = G^{n} of order |G| = n be fixed. For U, W ⊂ V = V (G) with U ∩ W = ∅, we write E(U, W) = E_{G}(U, W) for the set of edges of G that have one endvertex in U and the other in W. We set e(U, W) = e_{G}(U, W) = |E(U, W)|. The following notion will be needed in the sequel. Suppose 0 < η ≤ 1 and 0 < p ≤ 1. We say that G is η-uniform with density p if, for all U, W ⊂ V with U ∩ W = ∅ and |U|, |W | ≥ ηn, we have

|e_{G}(U, W) − p|U||W || ≤ ηp|U||W |.

Now let H ⊂ G be a spanning subgraph of G. For U, W ⊂ V with U ∩ W = ∅, let

d_{H,G}(U, W) = \{ \begin{matrix}e_{H}(U, W)/e_{G}(U, W) & if e_{G}(U, W) > 0 \\ 0 & if e_{G}(U, W) = 0. \end{matrix}

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

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

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

Lemma 2. For given ε > 0 and k_{0} ≥ 1, there are constants η = η(ε, k_{0}) > 0 and K_{0} = K_{0}(ε, k_{0}) ≥ k_{0} that depend only on ε and k_{0} such that, if G is an ηuniform graph and H ⊂ G is a spanning subgraph of G, then there is an (ε, H, G)- regular (ε, k)-equitable partition of V = V (G) with k_{0} ≤ k ≤ K_{0}. □

We now state two lemmas concerning random graphs. Here and below, if n ≥ 1 and 0 ≤ p = p(n) ≤ 1, we let G(n, p) be the probability space of the random graphs G_{p} = G_{n,p}. The following is immediate from standard estimates for tails of the binomial distribution.

Lemma 3. Let 0 < η ≤ 1 be given, and consider the random graph G_{p} = G_{n,p} ∈ G(n, p) with 0 < p = p(n) < 1. Put d = d(n) = np(n). Then, there is a constant d_{0} = d_{0}(η) such that, if d ≥ d_{0}, almost every G_{p} is η-uniform with density p. □

We now introduce another uniformity condition for graphs. Let G = G^{n} be a graph of order n, and suppose A > 0 and p > 0. Let d = pn. We say that G is (p, A)- uniform if, for all sets U, W ⊂ V (G) with U ∩ W = ∅ and 1 ≤ |U| ≤ |W | ≤ d|U|, we have

|e_{G}(U, W) − p|U||W || ≤ A{d|U||W |}^{1/2}.

The following lemma is proved in [7].

Lemma 4. Let d = d(n) > 0 be given, and put p = p(n) = d/n. Then a.e. G_{p} = G_{n,p} ∈ G(n, p) is (p, 20)-uniform. □

Let us remark that when dealing with (p, A)-uniform graphs of order n, we shall always have d = pn. Our last preliminary lemma concerns the size of induced subgraphs of (p, A)-uniform graphs. In this lemma and in the sequel, we write O_{1}(x) for a term y that satisfies |y| ≤ x.

Lemma 5. Suppose given A and p > 0, let G = G^{n} be a (p, A)-uniform graph, and suppose U ⊂ V (G). Then the size e(G[U]) of the graph G[U] induced by U in G satisfies

e(G[U]) = p\binom{|U|}{2} + O_{1}(Ad^{1/2}|U|).

Sketch of proof. It suffices to notice that

e(G[U]) = \binom{u}{2} \{⌊\frac{u}{2}⌋ ⌈\frac{u}{2}⌉\}^{−1} Ave_{S} e_{G}(S, U \ S),

where u = |U| and Ave_{S} e_{G}(S, U \ S) denotes the average of e_{G}(S, U \ S) when S runs over all S ⊂ U with |S| = ⌊u/2⌋. □

§2. The Main Result

2.1. Proof of the main result. Our aim in this section is to give the proof of Theorem 1. However, to state the key lemma in our argument, Lemma 6, we need to introduce some definitions and notation. Given a graph H and an integer ℓ ≥ 1, let us define the graph J = J(H) = J_{ℓ}(H) on V = V (H) by joining two distinct vertices x, y ∈ V in J if and only if there is an x–y path of length 2ℓ in H. Now suppose real constants A, C > 0 and 0 < γ_{0} ≤ 1 are fixed. Moreover, suppose G = G^{n} is a (p, A)-uniform graph, where p = p(n) ≥ Cn^{−1+1/2ℓ}, and let H ⊂ G be a subgraph of G of size e(H) ≥ γ_{0}e(G). The main lemma in the proof of Theorem 1, Lemma 6, states that e(J) is nearly as large as (e(H)/e(G))\binom{n}{2} provided C and n are sufficiently large with respect to ℓ, A, and γ_{0}.

Lemma 6. Let an integer ℓ ≥ 1, and reals 0 < δ ≤ 1, 0 < γ_{0} ≤ 1, and A > 0 be fixed. Then there is a constant C_{0} = C_{0}(ℓ, δ, γ_{0}, A) > 0 for which the following holds. Let G = G^{n} be a (p, A)-uniform graph with p = p(n) ≥ C_{0}n^{−1+1/2ℓ}, and let H ⊂ G be a subgraph of G with e(H) ≥ γ_{0}e(G). Then, provided n is sufficiently large, we have e(J_{ℓ}(H)) ≥ (1 − δ)(e(H)/e(G))\binom{n}{2}.

The proof of Lemma 6 is given in Section 2.2. In that section we also observe that this result is in fact best possible, and make a few remarks on the structure of the extremal subgraphs H for this lemma.

Let us now turn to the proof of Theorem 1. However, as this proof is somewhat technical in parts, we first present its main idea informally here to give the reader some feeling about the way we shall follow. Thus let ℓ ≥ 1 and 0 < η ≤ 1/2 be given, and let p = p(n) ≥ Cn^{−1+1/2ℓ} where C is a suitably large constant to be chosen later. Let us add the technical condition that p = p(n) = o(1) as n → ∞. We view the random graph G_{p} = G_{n,p} as a union of two independent random graphs G_{p_{1}}^{(1)} and G_{p_{1}}^{(2)}, both with edge-probability p_{1}. Thus, as we are assuming that p = o(1), we have in particular that p_{1} ∼ p/2. We decompose G_{p_{1}}^{(1)} even further, writing it as a union of k independent random graphs G_{p_{2}}^{(i)} (1 ≤ i ≤ k). Here k is a fixed large constant to be chosen later, and hence, since p = o(1), we have p_{2} ∼ p_{1}/k ∼ p/2k.

Now suppose F is a subset of edges of G_{p} with cardinality (1/2 + η)e(G_{p}) but spanning no (2ℓ + 1)-cycle. Assume that G_{p_{1}}^{(1)} and G_{p_{1}}^{(2)} contain γ_{1}e(G_{p_{1}}^{(1)}) and γ_{2}e(G_{p_{1}}^{(2)}) edges of F respectively. Note that γ_{1} + γ_{2} ∼ 1 + 2η. Moreover, amongst the G_{p_{2}}^{(i)} (1 ≤ i ≤ k), assume that G_{p_{2}}^{(j)} contains the maximum number of edges from F: we assume that it contains γ^{∗}e(G_{p_{2}}^{(j)}) of them, where clearly γ^{∗} ≳ γ_{1}. Now, assuming that C is large enough, we use Lemma 6 to deduce that the edges of F contained in G_{p_{2}}^{(j)} create at least about γ^{∗}\binom{n}{2} pairs of vertices of G_{p_{1}}^{(2)} that may not form edges in F, as G_{p}[F] contains no (2ℓ + 1)-cycle. Let us call such pairs of vertices prohibited. Now, with very large probability, say P̃, not many fewer than γ^{∗}e(G_{p_{1}}^{(2)}) edges of G_{p_{1}}^{(2)} join prohibited pairs, and hence not many more than (1 − γ^{∗})e(G_{p_{1}}^{(2)}) edges of G_{p_{1}}^{(2)} belong to F. However, the number of such edges is

γ_{2}e(G_{p_{1}}^{(2)}) ∼ (1 + 2η − γ_{1})e(G_{p_{1}}^{(2)}) ≳ (1 + 2η − γ^{∗})e(G_{p_{1}}^{(2)}).

This shows that actually considerably fewer than γ^{∗}e(G_{p_{1}}^{(2)}) edges of G_{p_{1}}^{(2)} may join prohibited pairs of vertices. Thus the probability that there is a set F ⊂ E(G_{p}) as above is at most 1 − P̃. It turns out that in fact P̃ is so large that 1 − P̃ can kill the number of possibilities for the set F ∩ E(G_{p_{2}}^{(j)}) ⊂ E(G_{p_{2}}^{(j)}), provided we pick k large enough. Thus we conclude that almost surely such a set F does not exist, and the theorem follows in this case, namely, when p = p(n) ≥ Cn^{−1+1/2ℓ} for some suitably large constant C and p = o(1).

We still have to deal with the case in which p = p(n) does not tend to 0 as n → ∞. Here we only sketch an argument based on the original regularity lemma of Szemerédi. Recall ℓ ≥ 1 and 0 < η ≤ 1/2 are given. Suppose 0 < ρ ≤ 1 and A > 0 are fixed constants and let G = G^{n} be a (ρ, A)-uniform graph of order n. Then a standard application of Szemerédi’s lemma gives that ex(G, C^{2ℓ+1}) ≤ (1/2+η)e(G) as long as n ≥ n_{0} for some constant n_{0} = n_{0}(ℓ, η, ρ, A). This implies that there is a function ρ_{0} = ρ_{0}(n) tending to 0 as n → ∞ such that the above statement remains true even if ρ is allowed to vary with n: it suffices that ρ = ρ(n) ≥ ρ_{0}(n). Since almost every random graph G_{p} = G_{n,p} is (p, 20)-uniform, Theorem 1 follows for p = p(n) ≥ ρ_{0}(n).

Let us now give the proof with all the details.

Proof of Theorem 1. Let A = 20, k = ⌈54η^{−3}⌉, ε = η/12, δ = η/4, γ_{0} = η, and let C = C(ℓ, η) = 2kC_{0} > 0, where C_{0} = C_{0}(ℓ, δ, γ_{0}, A) > 0 is as given in Lemma 6. We shall show that this choice of C will do in Theorem 1. Thus we fix p = p(n) ≥ Cn^{−1+1/2ℓ} and investigate C^{2ℓ+1}-free subgraphs of G_{p} ∈ G(n, p) of large size. As always, we may assume throughout that n is as large as we please. Also, owing to the remarks above, it suffices to consider the case in which p = p(n) = o(1).

We shall ‘generate’ G_{p} in k + 1 ‘rounds’ as follows. Let 0 < p_{1} = p_{1}(n) < 1, 0 < p_{2} = p_{2}(n) < 1 be such that 1−p = (1−p_{1})^{2}, 1−p_{1} = (1−p_{2})^{k}, and consider k +1 independent random graphs G_{p_{2}}^{(j)} ∈ G(n, p_{2}) (1 ≤ j ≤ k), G_{p_{1}}^{(2)} ∈ G(n, p_{1}). It is clear that { ⋃_{1≤j≤k} G_{p_{2}}^{(j)}} ∪ G_{p_{1}}^{(2)} is a random element of the space G(n, p). Below

we work with G = (G_{p_{2}}^{(1)}, …, G_{p_{2}}^{(k)}; G_{p_{1}}^{(2)}) ∈ Ω = { ∏_{1≤j≤k} G(n, p_{2})} × G(n, p_{1}), and

always let G_{p_{1}}^{(1)} = ⋃_{1≤j≤k} G_{p_{2}}^{(j)} and G_{p} = G_{p_{1}}^{(1)} ∪ G_{p_{1}}^{(2)}. The ‘bad’ event B whose probability we need to show approaches 0 as n → ∞ is that there should be a set F ⊂ E(G_{p}) with |F | > (1/2 + η)e(G_{p}) and G_{p}[F] ⊅ C^{2ℓ+1}.

Recall that we write O_{1}(x) for a term y that satisfies |y| ≤ x. Let Ω′ ⊂ Ω be the set of G = (G_{p_{2}}^{(1)}, …, G_{p_{2}}^{(k)}; G_{p_{1}}^{(2)}) ∈ Ω for which the G_{p_{2}}^{(j)} (1 ≤ j ≤ k) are (p_{2}, A)- uniform, e(G_{p_{2}}^{(j)}) = (1+O_{1}(ε))(p/2k)\binom{n}{2} (1 ≤ j ≤ k), e(G_{p_{1}}^{(i)}) = (1+O_{1}(ε))(p/2)\binom{n}{2} (i ∈ \{1, 2\}), and finally e(G_{p}) = (1 + O_{1}(ε))p\binom{n}{2}. Since ℙ(Ω′) = 1 − o(1) as n → ∞, below we always assume that our G are in Ω′. In particular, we concentrate on B′ = B ∩ Ω′.

Now, for each G ∈ B′, fix F = F (G) ⊂ E(G_{p}) with |F | > (1/2 + η)e(G_{p}) and G_{p}[F] ⊅ C^{2ℓ+1}. Moreover, let F_{i} = F_{i}(G) = F ∩ E(G_{p_{1}}^{(i)}), f_{i} = f_{i}(G) = |F_{i}|, and γ_{i} = γ_{i}(G) = f_{i}/e(G_{p_{1}}^{(i)}) for i ∈ {1, 2}, and similarly F^{(j)} = F^{(j)}(G) = F ∩ E(G_{p_{2}}^{(j)}), f^{(j)} = f^{(j)}(G) = |F^{(j)}|, and γ^{(j)} = γ^{(j)}(G) = f^{(j)}/e(G_{p_{2}}^{(j)}) for 1 ≤ j ≤ k. Let us now fix G ∈ B′.

Note that clearly |F | = |F (G)| ≤ f_{1} + f_{2}, and hence 1/2 + η < |F |/e(G_{p}) ≤ {e(G_{p_{1}}^{(1)})/e(G_{p})}γ_{1} + {e(G_{p_{1}}^{(2)})/e(G_{p})}γ_{2} ≤ (1 + 3ε)(γ_{1} + γ_{2})/2. Thus γ_{1} + γ_{2} ≥ (1 + 2η)/(1 + 3ε). Furthermore, we have that f_{1} ≤ f^{(1)} + ⋯ + f^{(k)}, and hence γ_{1} ≤ ((1+3ε)/k) ∑_{1≤j≤k} γ^{(j)}. Hence, putting γ^{∗} = γ^{∗}(G) = max_{1≤j≤k} γ^{(j)}, we have (1+ 3ε)(γ^{∗} +γ_{2}) ≥ (1+3ε)(γ_{1} +γ_{2}) ≥ 1+2η, and therefore γ^{∗} +γ_{2} ≥ (1+2η)/(1+3ε) ≥ 1 + η. Note that in particular γ^{∗} ≥ η. Now, for 1 ≤ j ≤ k, let B′_{j} = {G ∈ B′: γ^{(j)}(G) = γ^{∗}(G)}. Clearly B′ = ⋃_{1≤j≤k} B′_{j}, and hence it suffices to show that ℙ(B′_{j}) = o(1) as n → ∞ for all fixed 1 ≤ j ≤ k. Thus let us now fix 1 ≤ j ≤ k, and consider G ∈ B′_{j}. We have

ℙ(B′_{j}) = ∑_{G_{0}} ℙ(B′_{j} ∩ {G: G_{p_{2}}^{(j)} = G_{0}})
= ∑_{G_{0}} ℙ(B′_{j} | G_{p_{2}}^{(j)} = G_{0})ℙ(G_{p_{2}}^{(j)} = G_{0}) ≤ max_{G_{0}} ℙ(B′_{j} | G_{p_{2}}^{(j)} = G_{0}), (2)

where G_{0} ranges over all (p_{2}, A)-uniform graphs on V (G_{p}) with size e(G_{0}) = (1 + O_{1}(ε))(p/2k)\binom{n}{2}. We now fix one such G_{0} and argue that ℙ(B′_{j} | G_{p_{2}}^{(j)} = G_{0}) is small. For F_{0} ⊂ E(G_{0}), let P (j, G_{0}, F_{0}) = ℙ{G ∈ B′_{j} and F^{(j)}(G) = F_{0} | G_{p_{2}}^{(j)} = G_{0}}.

Then

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

(3)

Let us now fix F_{0} ⊂ E(G_{0}) with P (j, G_{0}, F_{0}) > 0. In particular, γ^{∗} = |F_{0}|/e(G_{0}) ≥ η = γ_{0}. It now follows from Lemma 6 that e(J_{ℓ}(G_{0}[F_{0}])) ≥ (1 − δ)γ^{∗}\binom{n}{2}.

Now, for each G ∈ Ω, let us put F′ = F′(G) = E(G_{p_{1}}^{(2)}) ∩ E(J_{ℓ}(G_{0}[F_{0}])), and let f′ = f′(G) = |F′|. Note that then, clearly, f′ = f′(G) (G ∈ Ω) has binomial distribution Bi(e(J_{ℓ}(G_{0}[F_{0}])), p_{1}) with parameters e(J_{ℓ}(G_{0}[F_{0}])) and p_{1}. Now suppose G ∈ B′, G_{p_{2}}^{(j)} = G_{0}, and F^{(j)} = F_{0}. Then, since F = F (G) does not span a (2ℓ+1)-cycle, we have F′(G)∩F_{2}(G) = ∅. Since F′(G)∪F_{2}(G) ⊂ E(G_{p_{1}}^{(2)}), we have f′(G) + γ_{2}(G)e(G_{p_{1}}^{(2)}) = f′(G) + f_{2}(G) ≤ e(G_{p_{1}}^{(2)}), and hence f′(G) ≤ (1 − γ_{2}(G))e(G_{p_{1}}^{(2)}). Therefore

P (j, G_{0}, F_{0}) ≤ ℙ{G ∈ Ω′ and f′(G) ≤ (1 − γ_{2}(G))e(G_{p_{1}}^{(2)})}
≤ ℙ \{f′(G) ≤ (1 − γ_{2}(G))(1 + ε)\frac{p}{2}\binom{n}{2}\} .  (4)

We now bound this last probability using that f′ = f′(G) ∼ Bi(e(J_{ℓ}(G_{0}[F_{0}])), p_{1}). Clearly, 𝔼(f′) ≤ p_{1}\binom{n}{2} ≤ p\binom{n}{2}. Moreover, recalling that γ^{∗} + γ_{2} ≥ 1 + η, we have

\begin{matrix}𝔼(f′) − (1 − γ_{2})(1 + ε)\frac{p}{2}\binom{n}{2} ≥ \{(1 − δ)γ^{∗} − (1 + ε)(1 − γ_{2})\}\frac{p}{2}\binom{n}{2} \\ ≥ (η − δ − ε)\frac{p}{2}\binom{n}{2} ≥ \frac{η}{3} p\binom{n}{2} ≥ \frac{η}{3} 𝔼(f′), \end{matrix}

and in particular 𝔼(f′) ≥ (ηp/3)\binom{n}{2}. Hence, by Hoeffding’s inequality [9] (see also inequality (5.6) in McDiarmid [12]), f′ ≤ (1−γ_{2})(1+ε)\frac{p}{2} \binom{n}{2} occurs with probability no greater than

ℙ \{f′ ≤ (1 − \frac{η}{3} ) 𝔼(f′)\} ≤ exp \{−\frac{η^{3}}{54}p\binom{n}{2}\} .

Thus, by (3) and (4), we have

ℙ(B′_{j} | G_{p_{2}}^{(j)} = G_{0}) ≤ 2^{(1+ε)(p/2k)\binom{n}{2}} exp \{−\frac{η^{3}}{54}p\binom{n}{2}\} ≤ exp \{−\frac{C}{352}η^{3}n^{1+1/2ℓ}\} .

Thus, by (2), we have ℙ(B′_{j}) = o(1) as n → ∞, as required. □

Remark. The idea of looking at G(n, p) as Ω = { ∏_{1≤j≤k} G(n, p_{2})} × G(n, p_{1}) in the above proof was inspired by Rödl and Ruciński [16], where a similar, slightly simpler, decomposition is used.

An immediate corollary of Theorem 1 is as follows.

Corollary 7. Let an integer ℓ ≥ 1 be fixed, and suppose ω = ω(n) → ∞ as n → ∞. Then if 0 < p = p(n) = ωn^{−1+1/2ℓ} ≤ 1 we almost surely have ex(G_{p}, C^{2ℓ+1}) = (1/2 + o(1))e(G_{p}). □

Remark. A simple alteration to the above proof of Theorem 1 gives in fact that, for any fixed ℓ ≥ 1 and 0 < η ≤ 1/2, there is a constant C′ = C′(ℓ, η) > 0 such that, if p = p(n) ≥ C′n^{−1+1/2ℓ}, then almost every G_{p} ∈ G(n, p) is such that any subgraph H ⊂ G_{p} with e(H) ≥ (1/2 + η)e(G_{p}) contains at least cηe(G_{p}) copies of C^{2ℓ+1}, where c > 0 is an absolute constant. This result is, however, rather weak for large p, as in this case one would expect the number of such copies to be much greater than e(G_{p}). This problem will be addressed elsewhere, as will the problem of investigating the structure of the extremal subgraphs for Theorem 1.

2.2. Proof of the main lemma. The main ingredients of the proof of Lemma 6 are a simple deterministic extremal result on edge-weighted graphs, Lemma 8, and the variant of Szemerédi’s lemma, Lemma 2, given in §1. Let a graph H = H^{k} of order k be given, and suppose γ̄ = (γ_{e})_{e∈E(H)} is a family of weights 0 ≤ γ_{e} ≤ 1 on the edges e ∈ E(H) of H. Given vertices x, y ∈ H, not necessarily distinct, let Z_{x,y} = Γ_{H}(x) ∩ Γ_{H}(y), and put

w(x, y) = w_{H,γ̄}(x, y) = \{ \begin{matrix}0 & if Z_{x,y} = ∅ \\ max\{γ_{zy}: z ∈ Z_{x,y}\} & if Z_{x,y} ≠ ∅. \end{matrix}

Also, for x ∈ H, let dγ̄(x) = d^{H,γ̄}(x) = ∑_{y∈Γ_{H}(x)} γ_{xy} be the γ̄-degree of x. For simplicity, put also γ̄(H) = ∑_{e∈E(H)} γ_{e}. Assume now that x = (x_{1}, …, x_{k}) is an ordering of the vertices of H. Then we let w(H, γ̄, x) = ∑_{1≤i≤j≤k} w(x_{i}, x_{j}). We shall in fact be interested in certain special orderings of V (H). Let us say that an ordering x = (x_{1}, …, x_{k}) of the vertices of H respects γ̄ if, for any 1 ≤ i ≤ k, the vertex x_{i} is a vertex of minimal γ̄_{i}-degree in H_{i} = H[x_{i}, …, x_{k}], the subgraph of H induced by {x_{i}, …, x_{k}}, where γ̄_{i} = (γ_{e})_{e∈E(H_{i})}. We may now give the first ingredient of the proof of Lemma 6.

Lemma 8. Let H = H^{k} be a graph of order k, and let γ̄ = (γ_{e})_{e∈E(H)} with 0 ≤ γ_{e} ≤ 1 (e ∈ E(H)) be given. Let x = (x_{1}, …, x_{k}) be an ordering of the vertices of H that respects γ̄. Then w(H, γ̄, x) ≥ γ̄(H).

Proof. We prove this lemma by induction on k. If k = 1, there is nothing to prove. Thus assume k ≥ 2, and suppose the lemma holds for smaller values of k. Consider H_{2} = H[x_{2}, …, x_{k}] and γ̄_{2} = (γ_{e})_{e∈E(H_{2})}. Clearly, x_{2} = (x_{2}, …, x_{k}) is an ordering of the vertices of H_{2} that respects γ̄_{2}, and hence by induction we have w(H_{2}, γ̄_{2}, x_{2}) ≥ γ̄_{2}(H_{2}). If Γ_{H}(x_{1}) = ∅, we have w(H, γ̄, x) = w(H_{2}, γ̄_{2}, x_{2}) ≥ γ̄_{2}(H_{2}) = γ̄(H), as required. Thus assume Γ_{H}(x_{1}) ≠ ∅, and pick z ∈ Γ_{H}(x_{1}). From our assumption on the ordering x, we have d^{H,γ̄}(z) ≥ d^{H,γ̄}(x_{1}). Therefore

\begin{aligned}w(H, γ̄, x) & ≥ w(H_{2}, γ̄_{2}, x_{2}) + ∑_{y∈Γ_{H}(z)} w(x_{1}, y) ≥ γ̄_{2}(H_{2}) + ∑_{y∈Γ_{H}(z)} γ_{zy} \\ & = γ̄_{2}(H_{2}) + d^{H,γ̄}(z) ≥ γ̄_{2}(H_{2}) + d^{H,γ̄}(x_{1}) = γ̄(H), \end{aligned}

as required. □

Our next lemma, Lemma 9, is the key observation that enables us to use Lemma 2 together with Lemma 8 to prove Lemma 6. To describe the context in which Lemma 9 applies, let an integer ℓ ≥ 1, and reals A, C, ε, μ > 0, and γ ≥ ρ > 0 be fixed. Assume that G = G^{n} is a (p, A)-uniform graph with p ≥ Cn^{−1+1/2ℓ}, and let H ⊂ G be a spanning subgraph of G. Let three pairwise disjoint sets V_{1}, V_{2}, V_{3} ⊂ V = V (G) with |V_{i}| = m ≥ μn (i ∈ {1, 2, 3}) be given. Furthermore, assume (V_{1}, V_{2}) and (V_{2}, V_{3}) are (ε, H, G)-regular pairs with d_{1,2} = d_{H,G}(V_{1}, V_{2}) ≥ ρ and d_{2,3} = d_{H,G}(V_{2}, V_{3}) ≥ γ. Roughly speaking, Lemma 9 states that the graph J = J(H) = J_{ℓ}(H) is such that e_{J_{ℓ}}(V_{1}, V_{3}) is nearly as large as γm^{2}, provided only that C and n are sufficiently large and ε is sufficiently small with respect to ℓ, A, μ, γ, and ρ.

In the proof of Lemma 9, we shall need the following simple definitions. Let J be a bipartite graph with a fixed bipartition, say V (J) = X∪Y. Then we shall say that J is a (b, f)-expander, and that it is (b, f)-expanding, if for all U ⊂ V (J) with |U| ≤ b and moreover U ⊂ X or U ⊂ Y we have |Γ_{J}(U)| ≥ f|U|. Also, if G is a graph and U, W ⊂ V (G) are two disjoint sets of vertices, we shall write G[U, W] for the bipartite subgraph of G with vertex classes U, W and with edge set E(U, W) = E_{G}(U, W).

Lemma 9. Let an integer ℓ ≥ 1, and reals A, C > 0, 0 < δ ≤ 1, 0 < μ ≤ 1, and 0 < ρ ≤ γ ≤ 1 be fixed. Let the graphs H ⊂ G, and J_{ℓ} = J_{ℓ}(H) be as above. Then, if C ≥ C_{0} = 32(A/δρμ)^{2} and 0 < ε ≤ ε_{0} = δρ/24, we have e(J_{ℓ}[V_{1}, V_{3}]) ≥ (1 − δ)γm^{2} provided n is sufficiently large.

Proof. We assume throughout that n is large, and in particular that G is η-uniform for η = εμ. We prove Lemma 9 by establishing three claims.

(1) There are sets V̄_{i} ⊂ V_{i} with |V̄_{i}| ≥ (1 − 2ε)m (i ∈ {1, 2, 3}) such that H_{1,2} = H[V̄_{1}, V̄_{2}] and H_{2,3} = H[V̄_{2}, V̄_{3}] have minimal degree δ(H_{1,2}) ≥ (1 − δ/4)d_{1,2}pm and δ(H_{2,3}) ≥ (1 − δ/4)d_{2,3}pm. To prove (1), one may use the argument in the proof of Lemma 2 of [7]. Here we only sketch an argument. To find the V̄_{i} (i ∈ {1, 2, 3}), we successively delete the vertices v ∈ V_{1} ∪ V_{2} ∪ V_{3} that violate the condition we seek. Then one may easily show that, owing to the (ε, H, G)-regularity of (V_{1}, V_{2}) and (V_{2}, V_{3}), this process finishes with the required sets V̄_{i} (i ∈ {1, 2, 3}).

Our next claim follows from (1) above and the (p, A)-uniformity of G.

(2) For (i, j) = (1, 2) and (i, j) = (2, 3), the bipartite graph H_{i,j} = H[V̄_{i}, V̄_{j}] is ((1 − δ/2)d_{i,j}m/f, f)-expanding for any 0 < f ≤ (δρμ/4A)^{2}d. To prove (2), fix (i, j) ∈ {(1, 2), (2, 3)}, let σ ∈ {i, j}, and suppose 0 < f ≤ (δρμ/4A)^{2}d. Pick U ⊂ V̄_{σ} with u = |U| ≤ (1−δ/2)d_{i,j}m/f, and put W = Γ_{H_{i,j}}(U). Assume for a contradiction that w = |W | < fu. Then, by (1) and the (p, A)- uniformity of G, we have

\begin{matrix}(1 − \frac{δ}{4}) d_{i,j}pmu ≤ e_{H_{i,j}}(U, W) ≤ e_{G}(U, W) \\ ≤ puw + A(duw)^{1/2} ≤ (1 − \frac{δ}{2}) d_{i,j}pmu + A(duw)^{1/2}. \end{matrix}

Thus (δ/4)d_{i,j}pmu ≤ A(duw)^{1/2}, and hence w ≥ (δρμ/4A)^{2}du ≥ fu, which is a contradiction. Thus |Γ_{H_{i,j}}(U)| ≥ f|U|, as required.

Our third and last claim is as follows.

(3) For all x ∈ V̄_{1}, we have |Γ_{J_{ℓ}}(x) ∩ V̄_{3}| ≥ (1 − 3δ/4)γm.

To check (3), note that d = pn = Cn^{1/2ℓ}, and hence that H_{1,2} and H_{2,3} are ((1 − δ/2)d_{i,j}m/f, f)-expanding for 0 < f ≤ 2n^{1/2ℓ}. Now fix x ∈ V̄_{1}, and let X_{0} = {x}. Let X_{1}, X_{2}, …, X_{2ℓ−1} be such that n^{i/2ℓ} ≤ |X_{i}| ≤ 2n^{i/2ℓ} for 1 ≤ i ≤ 2ℓ − 1, and X_{1} ⊂ Γ_{H_{1,2}}(X_{0}), X_{2} ⊂ Γ_{H_{1,2}}(X_{1}) \ X_{0}, …, X_{2ℓ−1} ⊂ Γ_{H_{1,2}}(X_{2ℓ−2}) \ (X_{1} ∪ ⋯ ∪ X_{2ℓ−3}). Finally, let X_{2ℓ} = Γ_{H_{2,3}}(X_{2ℓ−1}). From the expansion property (2) of the H_{i,j}, the result follows.

Lemma 9 follows from (1) and (3) above, as e(J_{ℓ}[V_{1}, V_{3}]) ≥ (1 − 3δ/4)γm|V̄_{1}| ≥ (1 − δ)γm^{2}. □

We are now ready to prove Lemma 6, the main lemma in the proof of Theorem 1.

Proof of Lemma 6. Let an integer ℓ ≥ 1, and reals 0 < δ ≤ 1, 0 < γ_{0} ≤ 1, and A > 0 be fixed. We may clearly assume that δ ≤ 15γ_{0}. Let ε = γ_{0}δ^{2}/2200 and k_{0} = ⌈1/ε⌉, and let 0 < η = η(ε, k_{0}) ≤ 1 and K_{0} = K_{0}(ε, k_{0}) ≥ k_{0} be as given in Lemma 2. We may and shall assume that η ≤ ε/2K_{0}. Let ρ = γ_{0}δ/15 ≤ 1 and C_{0} = C_{0}(ℓ, δ, γ_{0}, A) = 10^{7}(AK_{0}/δ^{2}γ_{0})^{2}. We shall show that this C_{0} will do in our lemma. Thus, let H ⊂ G be a subgraph of a (p, A)-uniform graph G = G^{n} with e(H) ≥ γ_{0}e(G), where p = p(n) ≥ C_{0}n^{−1+1/2ℓ}. Let γ = e(H)/e(G). We now investigate J_{ℓ} = J_{ℓ}(H). We may clearly assume that H is a spanning subgraph of G. Furthermore, we may assume throughout that n is larger than some suitably chosen large constant, and in particular that G = G^{n} is η-uniform with density p (cf. Lemma 5). We now apply Lemma 2 to H ⊂ G to obtain an ε-equitable (ε, H, G)- regular partition P = (V_{i})_{0}^{k} of V = V (G) with k_{0} ≤ k ≤ K_{0}. For convenience, let m = |V_{i}| (1 ≤ i ≤ k).

We now define a graph H^{∗} on [k] by letting ij ∈ E(H^{∗}) (1 ≤ i < j ≤ k) if and only if (V_{i}, V_{j}) is an (ε, H, G)-regular pair with d_{H,G}(V_{i}, V_{j}) ≥ ρ. Moreover, for e = ij ∈ E(H^{∗}), let γ_{e} = d_{H,G}(V_{i}, V_{j}), and let γ̄ = (γ_{e})_{e∈E(H^{∗})}. We may and shall assume that the natural ordering x = (1, …, k) of the vertices of H^{∗} respects γ̄. Finally, let us define a spanning subgraph H′ ⊂ H of H by letting xy ∈ E(H) be an edge of H′ if and only if x ∈ V_{i} and y ∈ V_{j} for some 1 ≤ i < j ≤ k with ij ∈ E(H^{∗}).

(1) We have e(H′) ≥ (1 − δ/6)γp\binom{n}{2}.

We first estimate |E(H) \ E(H′)|. From the (p, A)-uniformity of G it follows that, for any W ⊂ V (G) with |W | ≥ ηn, we have e(G[W]) ≤ (1 + η)p\binom{|W |}{2} if n is large enough. Hence e(H[V_{0}]) ≤ ε^{2}pn^{2}. Moreover, writing d = pn as usual, we have that e_{G}(V_{0}, V \ V_{0}) is at most

p|V_{0}||V \ V_{0}| + A{d|V_{0}||V \ V_{0}|}^{1/2} ≤ εpn^{2} + And^{1/2} ≤ 2εpn^{2}

for large enough n. Now note that ∑ e_{G}(V_{i}, V_{j}) with the sum over all 1 ≤ i < j ≤ k such that (V_{i}, V_{j}) is not (ε, H, G)-regular is at most ε\binom{k}{2}(1 + η)pm^{2} ≤ εpn^{2}. Also, ∑ e_{H}(V_{i}, V_{j}) with the sum extended over all 1 ≤ i < j ≤ k such that d_{H,G}(V_{i}, V_{j}) ≤ ρ is at most ρ\binom{k}{2}(1+η)pm^{2} ≤ ρpn^{2}. Finally, for large enough n, we have that ∑_{1≤i≤k} e(G[V_{i}]) ≤ k(1+η)p\binom{m}{2} ≤ pn^{2}/k. Therefore |E(H)\E(H′)| ≤ (4ε + ρ + 1/k)pn^{2} ≤ (5ε + ρ)pn^{2} if n is sufficiently large. On the other hand, we have e(H) = γe(G) ≥ γ(1 − η)p\binom{n}{2}. Thus

\begin{aligned}e(H′) & ≥ γ(1 − η)p\binom{n}{2} − 2(6ε + ρ)p\binom{n}{2} \\ & = (1 − η − 12\frac{ε}{γ} − 2\frac{ρ}{γ} ) γp\binom{n}{2} ≥ (1 − \frac{δ}{6}) γp\binom{n}{2}. \end{aligned}

We now look at (H^{∗}, γ̄). As in Lemma 8, let γ̄(H^{∗}) = ∑_{e∈E(H^{∗})} γ_{e}.

(2) We have γ̄(H^{∗}) ≥ (1 − δ/2)γk^{2}/2. To prove (2), note that

\begin{aligned}(1 − \frac{δ}{6}) γp\binom{n}{2} ≤ e(H′) & = ∑_{e=ij∈E(H^{∗})} γ_{e}e_{G}(V_{i}, V_{j}) \\ & ≤ (1 + η)pm^{2}γ̄(H^{∗}) ≤ (1 + η)p\frac{n^{2}}{k^{2}} γ̄(H^{∗}). \end{aligned}

Therefore γ̄(H^{∗}) ≥ {(1 − δ/6)/(1 + η)}(1 − 1/n)γk^{2}/2 ≥ (1 − δ/2)γk^{2}/2.

We may now complete the proof of our lemma.

(3) We have e(J_{ℓ}(H)) ≥ (1 − δ)γ\binom{n}{2}. Let 1 ≤ i < j ≤ k. By Lemma 9, applied with δ/6, we have that e(J_{ℓ}[V_{i}, V_{j}]) ≥ (1−δ/6)w(i, j)m^{2}, where w(i, j) = w_{H^{∗},γ̄}(i, j) is as defined before Lemma 8. Thus, by (2) and Lemma 8, we have

e(J_{ℓ}(H)) ≥ ∑_{1≤i<j≤k} e(J_{ℓ}[V_{i}, V_{j}]) ≥ (1 − \frac{δ}{6}) m^{2}\{w(H^{∗}, γ̄, x) − ∑_{1≤i≤k} w(i, i)\}

≥ (1 − \frac{δ}{6}) m^{2}γ̄(H^{∗}) − km^{2} ≥ \frac{1}{2} (1 − \frac{2δ}{3} ) γk^{2}m^{2} − \frac{n^{2}}{k}

≥ \frac{1}{2}(1 − ε)^{2} (1 − \frac{2δ}{3} ) γn^{2} − εn^{2} ≥ (1 − δ)γ\binom{n}{2},

as required. □

Remark. Lemma 6 is essentially best possible in the sense that the lower bound for e(J_{ℓ}(H)) cannot be substantially improved. In fact, any graph G on n vertices contains many subgraphs H for which e(J_{ℓ}(H)) is not greater than (e(H)/e(G))\binom{n}{2}. To mention just two examples of quite different nature, first fix any 1 ≤ k ≤ n and let H = H^{k} be a k-vertex subgraph of G of maximum size, and note that then e(H) ≥ e(G)\binom{k}{2}\binom{n}{2}^{−1} whereas trivially e(J_{ℓ}(H)) ≤ \binom{k}{2}. Now suppose 1 ≤ k ≤ n/2 and let H = H^{2k} be a balanced bipartite subgraph of G of order 2k and maximum size. Then e(H) ≥ 2e(G)k^{2}/n^{2} whilst e(J_{ℓ}(H)) ≤ k^{2}. From these two examples, we also see that the ‘extremal’ or ‘near-extremal’ subgraphs H for Lemma 6 may have quite a varied structure.

§3. Deterministic Consequences

In this section we give a few results concerning the existence, for any given 0 < ε ≤ 1/2 and ℓ ≥ 1, of very sparse graphs G that satisfy G →_{1/2+ε} C^{2ℓ+1}.

If H is a graph of order |H| ≥ 3 and size e(H) ≥ 1, its 2-density is d_{2}(H) = (e(H)−1)/(|H|−2). In particular, the 2-density of the (2ℓ+1)-cycle C^{2ℓ+1} (ℓ ≥ 1) is d_{2}(C^{2ℓ+1}) = 2ℓ/(2ℓ − 1). For integers k ≥ 3 and ℓ ≥ 1, let H_{k,ℓ} be the family of all graphs H with 3 ≤ |H| ≤ k, e(H) ≥ 1, and d_{2}(H) > d_{2}(C^{2ℓ+1}). Also, let Forb(H_{k,ℓ}) be the collection of all graphs G that are H-free for all H ∈ H_{k,ℓ}.

Theorem 10. Let 0 < ε ≤ 1/2 and integers k ≥ 3 and ℓ ≥ 1 be fixed. Then there exists a graph G = G_{ε,k,ℓ} ∈ Forb(H_{k,ℓ}) such that G →_{1/2+ε} C^{2ℓ+1}.

Proof. Put η = ε/2 and let C = C(ℓ, η/2) be as given in Theorem 1. Let p = p(n) = Cn^{−1+1/2ℓ}, and consider G_{p} ∈ G(n, p). Theorem 1 then tells us that G_{p} →_{1/2+η} C^{2ℓ+1} almost surely, and it is a standard matter to check that a.e. G_{p} contains, very generously, at most (ε/2)e(G_{p}) copies of elements of H_{k,ℓ} as subgraphs. Fix a G_{p} satisfying both conditions above, and let G ⊂ G_{p} be a spanning subgraph of G_{p} obtained from G_{p} by the removal of at least one edge from each subgraph of G_{p} that is a copy of an element of H_{k,ℓ}, and such that e(G) ≥ (1 − ε/2)e(G_{p}). Then clearly G ∈ Forb(H_{k,ℓ}). Moreover, we have that G →_{1/2+ε} C^{2ℓ+1}. To see this, suppose J ⊂ G is a subgraph of G with e(J) ≥ (1/2 + ε)e(G). Then e(J) ≥ (1/2)(1 + 2ε)(1 − ε/2)e(G_{p}) ≥ (1/2)(1 + ε)e(G_{p}). As G_{p} →_{(1+ε)/2} C^{2ℓ+1}, the graph J must contain a (2ℓ + 1)-cycle and we are done. □

We now single out a corollary to Theorem 10. In Corollary 11 below, the property that G belongs to Forb(H_{k,ℓ}) in Theorem 10 is replaced by a collection of simpler and more concrete conditions. For instance, one of these conditions is that the girth g(G) of G should be at least 2ℓ + 1. To state another condition that appears in Corollary 11, we need to introduce a definition.

Let G be a graph and ℓ ≥ 1 a positive integer. Suppose C_{1}, …, C_{h} (h ≥ 2) are distinct (2ℓ + 1)-cycles of G, and e_{1} ∈ E(C_{1}), …, e_{h−1} ∈ E(C_{h−1}) are h − 1 edges of G such that E(C_{i}) ∩ ⋃_{1≤j<i} E(C_{j}) = {e_{i−1}} (2 ≤ i ≤ h). Then we say that (C_{1}, …, C_{h}) is a (h, C^{2ℓ+1})-path in G. Now assume that (C_{1}, …, C_{h}) is a (h, C^{2ℓ+1})-path in G and that the edge e ∈ E(G) joins a vertex in V (C_{1}) \ ⋃_{1<j≤h} V (C_{j}) to a vertex in V (C_{h})\⋃_{1≤i<h} V (C_{i}). We then say that (C_{1}, …, C_{h}; e) is a (h, C^{2ℓ+1})-cycle in G.

It is immediate to check that if (C_{1}, …, C_{h}) is a (h, C^{2ℓ+1})-path, then H = ⋃_{1≤j≤h} C_{j} has 2-density d_{2}(H) ≥ d_{2}(C^{2ℓ+1}). Also, if (C_{1}, …, C_{h}; e) is a (h, C^{2ℓ+1})- cycle, then H′ = H + e has 2-density d_{2}(H′) > d_{2}(C^{2ℓ+1}).

Corollary 11. For any 0 < ε ≤ 1/2 and integers k ≥ 2 and ℓ ≥ 1, there is a graph G = G_{ε,k,ℓ} such that (i) g(G) = 2ℓ + 1, (ii) no two (2ℓ + 1)-cycles in G share more than two vertices, and if two such cycles do share two vertices then they also share an edge, (iii) G contains no (h, C^{2ℓ+1})-cycles for any 2 ≤ h ≤ k, and (iv) G →_{1/2+ε} C^{2ℓ+1}. □

Acknowledgements. The authors are indebted to an anonymous referee for a very meticulous reading.

References

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

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

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

4. Erdős, P., Stone, A.H., On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946), 1089–1091.

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

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

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

8. , Turán’s extremal problem in random graphs: forbidding even cycles (submitted).

9. Hoeffding, W., Probability inequalities for sums of bounded random variables, Jour. Amer. Statistical Assoc. 58 (1963), 13–30.

10. Kohayakawa, Y., The regularity lemma of Szemerédi for sparse graphs, manuscript, 1993.

11. Łuczak, T., Ruciński, A., Voigt, B., Ramsey properties of random graphs, J. Combinatorial Theory (B) 56 (1992), 55–68.

12. McDiarmid, C.J.H., On the method of bounded differences, Surveys in Combinatorics 1989, London Mathematical Society Lecture Notes Series 141 (Siemons, J., ed.), Cambridge University Press, Cambridge, 1989, pp. 148–188.

13. Rödl, V., Personal communication, July 1993.

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

15. , Random graphs with monochromatic triangles in every edge colouring, Random Structures and Algorithms 5 (1994), 253–270.

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

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

Department of Combinatorics and Optimisation, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1

E-mail address: <pehaxell@math.uwaterloo.ca>

Instituto de Matemática e Estatística, Universidade de São Paulo, Caixa Postal 20570, 01452–990 São Paulo SP, Brazil

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

Mathematical Institute of the Polish Academy of Sciences, Poznań, Poland, on leave from the Department of Discrete Mathematics, Adam Mickiewicz University, ul. Matejki 48/49, 60–769 Poznań, Poland

E-mail address: <tomasz@plpuam11.bitnet>, <tomasz@mathcs.emory.edu>