An extremal problem for random graphs and the number of graphs with large even-girth

Y. Kohayakawa^{∗}

Instituto de Matemática e Estatística, Universidade de São Paulo Rua do Matão 1010, 05508–900 São Paulo, 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

A. Steger^{§}

Institut für Informatik, Technische Universität München 80290 München, Germany

        E-mail address: steger@informatik.tu-muenchen.de

Abstract

We study the maximal number of edges a C_{2k}-free subgraph of a random graph G_{n,p} may have, obtaining best possible results for a range of p = p(n). Our estimates strengthen previous bounds of Füredi [12] and Haxell, Kohayakawa, and Łuczak [13]. Two main tools are used here: the first one is an upper bound for the number of graphs with large even-girth, i.e., graphs without short even cycles, with a given number of vertices and edges, and satisfying a certain additional pseudorandom condition; the second tool is the powerful result of Ajtai, Komlós, Pintz, Spencer, and Szemerédi [1] on uncrowded hypergraphs as given by Duke, Lefmann, and Rödl [7].

AMS subject classification code (1991): 05A16, 05C35, 05C38, 05C80 Key words and phrases: Turán’s extremal problem, forbidden subgraphs, cycles, random graphs, asymptotic enumeration

∗Partially supported by FAPESP (Proc. 93/0603–1 and 96/04505–2) and by CNPq (Proc. 300334/93–1). Part of this work was done while this author was visiting the other two authors at Universität Bonn, supported by a DAAD–University of São Paulo exchange programme. Part of the revision was carried out with the support of PROBRAL project 026/95, a CAPES–DAAD exchange programme, and PRONEX project 107/97.

§Partially supported by DFG grant Pr 296/2–1.

1 Introduction

A classical area of extremal graph theory concerns the asymptotic structure of nvertex graphs G = G^{n} that do not contain an isomorphic copy of a given graph H as a subgraph. A basic problem is to determine or estimate the maximal number of edges ex(n, H) that such a graph G may have. The answer to this problem is beautiful: the celebrated Erdős–Stone Theorem implies that, as n → ∞, we have

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

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

Thus the situation for graphs H with χ(H) ≥ 3 is quite well understood. Unfortunately, the same cannot be said about the case in which we forbid a bipartite graph H in our G = G^{n}. Indeed, in this case, usually referred to as the degenerate case, relation (1) only tells us that ex(n, H) = o(n^{2}), and obtaining any further information on ex(n, H) is usually very hard. To see the level of difficulty here, recall that an old and very well known unresolved conjecture of Erdős and Simonovits [10] states that ex(n, C_{2k}) ≍ n^{1+1/k} for all k ≥ 2. Here, as usual, C_{2k} denotes the cycle of length 2k, and for two functions f and g we write f ≍ g if f = O(g) and g = O(f). Bondy and Simonovits [6] have proved the upper bound of O(n^{1+1/k}).

In this note we are concerned with the following variant of the problems above. For graphs G and H, write ex(G, H) for the maximum number of edges an H-free subgraph of G may have. Thus, writing K_{n} for the complete graph on n vertices, we have ex(n, H) = ex(K_{n}, H). We are interested in ex(G, H) for a ‘typical’ graph G and a fixed graph H, where by a ‘typical’ G we mean the random graph G_{n,p}, the graph on n labelled vertices whose edges are independently present with probability p = p(n). The random variable ex(G_{n,p}, H) was first considered by Babai, Simonovits, and Spencer [2] who treated the case in which H has chromatic number 3 and p is a constant. Here, however, we concentrate on very small values of p and on the very specific degenerate case focused on in the Erdős–Simonovits conjecture, i.e., when H = C_{2k} (k ≥ 2).

The behaviour of ex(G_{n,p}, C_{4}) was investigated by Füredi [12] in relation to a Ramsey type problem posed by Erdős and Faudree [9]. For general k ≥ 2, Haxell, Kohayakawa, and Łuczak [13] showed that, for all p = p(n) = ωn^{−1+1/(2k−1)} with ω = ω(n) → ∞ as n → ∞, we have

ex(G_{n,p}, C_{2k}) = o(|E(G_{n,p})|)  (2)

almost surely, i.e., with probability tending to 1 as n → ∞. Thus, provided p = p(n) is sufficiently large, we are again dealing with a degenerate extremal problem: even a fraction approaching 0 of the edges of a typical G_{n,p} spans a C_{2k}.

The condition on p = p(n) for (2) to hold, namely, that pn^{1−1/(2k−1)} → ∞ as n → ∞, deserves a quick remark. A simple first moment calculation gives that, for p = p(n) = o(n^{−1+1/(2k−1)}), the number of 2k-cycles in a typical G_{n,p} is negligible compared with |E(G_{n,p})|. Thus, as a simple deletion argument shows, we have ex(G_{n,p}, C_{2k}) = (1 − o(1))|E(G_{n,p})| almost surely for such a p = p(n) (a more precise result is described in Section 5). For these and related results concerning random graphs that we tacitly assume throughout the rest of the paper, cf. Bollobás [5].

The main result in this paper strengthens (2) by determining ex(G_{n,p}, C_{2k}) up to a constant factor for a polynomial range of p = p(n) starting at the threshold n^{−1+1/(2k−1)} (see Theorem 1). Unfortunately, our technique breaks down for p too far above this threshold, although the situation is better for k = 2 (see Theorem 2). As a consequence of our sharp result for small enough p, we may deduce an explicit bound for ex(G_{n,p}, C_{2k}) improving (2) for the whole range of p (see Corollary 3). We remark that our sharp estimates for ex(G_{n,p}, C_{2k}) also imply that, surprisingly, this function contains a logarithmic factor. In classical extremal graph theory, a conjecture of Erdős and Simonovits says that logarithmic factors do not occur; cf., e.g., [20]. It has already been shown that this conjecture does not hold for hypergraphs: Frankl and Füredi [11] have constructed a 5-uniform hypergraph H with no exponent, i.e., for which there exists no β such that ex(n, H) ≍ n^{β}.

Our method for obtaining the upper bound for ex(G_{n,p}, C_{2k}) is based on a technical lemma concerning the number of certain graphs with no short even cycles. Let the even-girth of a graph be the length of its shortest even cycle. To estimate ex(G_{n,p}, C_{2k}) from above, we estimate the number of certain nvertex graphs with even-girth larger than 2k and with a given number T = T (n) of edges; see Lemma 5 below. On the other hand, we deduce our lower bound for ex(G_{n,p}, C_{2k}) from a powerful result of Ajtai, Komlós, Pintz, Spencer, and Szemerédi [1] on ‘uncrowded hypergraphs’ as given in Duke, Lefmann, and Rödl [7].

The method used in the proof of Lemma 5, coupled with another idea, gives an estimate for the total number of n-vertex graphs with even-girth larger than 2k. Theorem 4 gives this estimate. We remark that this result was proved in Kreuter [18], but while writing this note we were kindly informed that a weaker form of this theorem was independently proved by Kleitman and Wilson [15]. Kleitman and Wilson achieve the same estimate for the number of graphs of even-girth larger than 2k which, in addition, contain no odd cycles of length smaller than k. Further enumeration results are proved in [15]; in particular, the long-standing problems of estimating the number of C_{6}-free graphs and of C_{8}-free graphs are resolved in [15]. Finally, we mention that further results concerning ex(G_{n,p}, H) are obtained in Haxell, Kohayakawa, and Łuczak [14], and Kohayakawa, Łuczak, and Rödl [17].

2 Main results

We state our main results in this section. Recall that we may assume that p is at least of order n^{−1+1/(2k−1)}, for otherwise we have ex(G_{n,p}, C_{2k}) = (1 − o(1))|E(G_{n,p})|. It turns out that our results are best formulated in terms of the ‘multiplicative excess’ of p = p(n) over the threshold n^{−1+1/(2k−1)}. Thus, we put

α = α(n) = p/n^{−1+1/(2k−1)},  (3)

so that p = αn^{−1+1/(2k−1)}. Our first result is the following. As usual, for any graph G, we write e(G) for the number of edges in G.

Theorem 1 Let k ≥ 2 be an integer and let p = p(n) = αn^{−1+1/(2k−1)} be such that

2 ≤ α ≤ n^{1/(2k−1)^{2}}.

Then

ex(G_{n,p}, C_{2k}) ≍ \frac{(log α)^{1/(2k−1)}}{α} e(G_{n,p}).  (4)

For C_{4} we can show the following slightly stronger theorem, holding for a wider range of p.

Theorem 2 Let δ > 0 be given and p = p(n) = αn^{−2/3} such that 2 ≤ α ≤ n^{1/3−δ}. Then

ex(G_{n,p}, C_{4}) ≍ \frac{(log α)^{1/3}}{α} e(G_{n,p}).

Unfortunately, the techniques used in the proofs of Theorems 1 and 2 break down for large p. Nevertheless, for larger p, Theorem 1 implies the following result, which strengthens (2) above.

Corollary 3 There exists a constant c_{k} that depends only on k such that, for p = p(n) ≥ n^{−1+1/(2k−1)+1/(2k−1)^{2}}, we almost surely have

ex(G_{n,p}, C_{2k}) ≤ \frac{c_{k}(log n)^{1/(2k−1)}}{n^{1/(2k−1)^{2}}} e(G_{n,p}).

The heart of the proof of the upper bounds in these theorems is a somewhat technical upper bound on the number of n-vertex graphs with even-girth larger than 2k, a given number T = T (n) of edges and satisfying some additional constraints. The precise statement of this lemma is deferred to the next section (Lemma 5). An idea used in the proof of this lemma first appears in Kreuter [18], where the following generalization of a theorem of Kleitman and Winston [16] is proved. For an integer n and a family of graphs L, denote by Forb_{n}(L) the set of all n-vertex graphs containing no graph from L as a subgraph.

Theorem 4 [18] Let k ≥ 2 be a fixed integer and put c_{k} = 0.54k + 1.5. Then, as n → ∞, we have

|Forb_{n}(C_{4}, …, C_{2k})| ≤ 2^{c_{k}n^{1+1/k}(1+o(1))}.

In Section 4 we include a sketch of the proof of Theorem 4. Note that for k = 2, 3 and 5, Theorem 4 is, apart from the factor c_{k} in the exponent, best possible because, for these values of k, there are {C_{4}, …, C_{2k}}-free graphs with Θ(n^{1+1/k}) edges (see Benson [3] and Wenger [22]) and 2^{ex(n,{C_{4},...,C_{2k}})} is an obvious lower bound for |Forb_{n}(C_{4}, …, C_{2k})|. For general k we remark that a conjecture of Erdős and Simonovits [10] states that ex(n, {C_{4}, …, C_{2k}}) = Ω(n^{1+1/k}).

It is crucial for the proof of Theorem 4 that the graphs under consideration contain no small even cycles. A special case of a more general conjecture of Erdős (cf., e.g., [8]) states that in fact

|Forb_{n}(C_{2k})| = 2^{O(n^{1+1/k})}  (5)

should hold. In the forthcoming paper of Kleitman and Wilson [15], inequality (5) is proved for k = 3 and k = 4.

3 Proofs

3.1 Proof of the upper bounds

The proofs of the upper bounds in Theorems 1 and 2 are based on a technical lemma, which we shall now state. It gives an upper bound for the number of nvertex graphs with a given number T = T (n) of edges, even-girth larger than 2k, and satisfying a certain pseudorandom condition, i.e., a condition satisfied by certain random graphs. The pseudorandom condition is introduced to allow us to obtain a bound that takes into account the number of edges T.

For given integers n and T and a set of graphs L, define f(L, n, T) to be the number of graphs on n labelled vertices with T edges and not containing any graph from L as a subgraph. We want to bound f({C_{4}, C_{6}, …, C_{2k}}∪L_{k}, n, T), where L_{k} is a certain finite family of ‘dense’ graphs.

The families L_{k} (k ≥ 2) are defined as follows. We first put L_{2} = ∅. For k ≥ 3, we let L_{k} be the set of all graphs H on at most (4k)^{4} vertices satisfying

e(H) > (1 − \frac{1}{2k − 1} − \frac{1}{(2k − 1)^{2}} )^{−1} v(H),

where v(H) = |V (H)| and e(H) = |E(H)|.

For any fixed k ≥ 2, if p ≤ n^{−1+1/(2k−1)+1/(2k−1)^{2}}, the expected number of graphs from L_{k} in G_{n,p} is o(1). The following lemma will therefore enable us to prove an upper bound on the number of {C_{4}, …, C_{2k}}-free graphs that are subgraphs of a typical G_{n,p} for such a p = p(n).

Lemma 5 Let an integer k ≥ 2 be fixed. Define the constants c_{1} = 2(8k)^{6}, c_{2} = (2(k − 1)(8k)^{8k}/(2k − 1))^{1/(2k−1)} and ε = 24/(13(8k)^{8k+1}), and let T = βn^{1+1/(2k−1)} be an integer. Then, if c_{1} < β < c_{2}(log n)^{1/(2k−1)}, we have

f(\{C_{4}, …, C_{2k}\} ∪ L_{k}, n, T) < (\frac{n^{2}}{T} exp \{−εβ^{2k−1}\})^{T} ,

and, if β ≥ c_{2}(log n)^{1/(2k−1)}, we have

f(\{C_{4}, …, C_{2k}\} ∪ L_{k}, n, T) < (\frac{4en^{k+1}}{T^{k}} )^{T} exp \{ε^{−1}(n log n)^{1+1/(2k−1)}\} .

The proof of Lemma 5 is postponed until Section 3.3. From the first part of Lemma 5 we may easily deduce the following theorem, which proves the upper bound of Theorem 1.

Theorem 6 For any given integer k ≥ 2, there exists a constant C_{0} = C_{0}(k) such that the following holds. Suppose α = α(n) ≥ 2 is such that α < n^{1/13} if k = 2 and α < n^{1/(2k−1)^{2}} if k ≥ 3. Let p = p(n, α) = αn^{−1+1/(2k−1)}. Then with probability 1 − o(n^{−1/(2k−1)}) we have

ex(G_{n,p}, C_{2k}) ≤ C_{0}n^{1+1/(2k−1)}(log α)^{1/(2k−1)}.  (6)

Proof. Observe first that it is enough to prove the theorem for α ≥ α_{0} for some constant α_{0}. When this case is settled, the theorem follows from the fact that ex(G_{n,p}, C_{2k}) is increasing in probability with respect to p and by suitably altering the constant C_{0}.

Choose C_{0} such that \frac{1}{2}εC_{0}^{2k−1} = 1 and α_{0} such that C_{0}(\frac{1}{2} log α_{0})^{1/(2k−1)} > c_{1}, where ε = ε(k) and c_{1} = c_{1}(k) are the constants from Lemma 5. Let α = α(n) and p = p(n, α) be as in the statement of our theorem. Before applying Lemma 5 we first show that with high probability G_{n,p} does not contain too many even cycles of length at most 2k − 2. The expected number of these cycles in G_{n,p} is bounded from above by

∑_{l=2}^{k−1} \frac{n^{2l}}{4l} p^{2l} ≤ (n^{1/(2k−1)+1/(2k−1)^{2}})^{2(k−1)} = o(n).

Now let β = C_{0}(\frac{1}{2} log α)^{1/(2k−1)} and T = βn^{1+1/(2k−1)}. Then, by Markov’s inequality, with probability 1−o(n^{−1/(2k−1)}) our G_{n,p} contains o(T) even cycles of length at most 2k − 2.

Now, one may check that β = C_{0}(\frac{1}{2} log α)^{1/(2k−1)} < c_{2}(log n)^{1/(2k−1)}, where c_{2} is as defined in Lemma 5. Hence, by the first case of that lemma, the expected number of {C_{4}, …, C_{2k}} ∪ L_{k}-free subgraphs of G_{n,p} with T edges is

f({C_{4}, …, C_{2k}} ∪ L_{k}, n, T)p^{T}

≤ (\frac{n^{2}}{T} exp \{−\frac{1}{2}εC_{0}^{2k−1} log α\} αn^{−1+1/(2k−1)})^{T}

≤ (\frac{1}{C_{0}(\frac{1}{2} log α)^{1/(2k−1)}} )^{T} = o(n^{−1/(2k−1)}).

Thus with probability 1 − o(n^{−1/(2k−1)}) every G_{n,p} (i) contains o(T) copies of graphs from L_{k} (this follows again from Markov’s inequality and the remarks of the beginning of this section), (ii) contains o(T) even cycles of length smaller than 2k, and (iii) contains no {C_{4}, …, C_{2k}} ∪ L_{k}-free subgraph with T edges. To finish the proof, we simply observe that a graph satisfying (i), (ii), and (iii) above cannot contain a C_{2k}-free subgraph with T + Ω(T) edges: if H is such a subgraph, by (i) and (ii) we are able delete some edges from H to obtain a {C_{4}, …, C_{2k}}∪L_{k}-free subgraph of G_{n,p} with T edges, contradicting (iii). □

Proof of Corollary 3. We can assume that p = O(n^{−1+1/k+1/(2k)^{2}}) for otherwise the statement follows because of the deterministic bound ex(n, C_{2k}) = O(n^{1+1/k}).

In order to be able to apply Theorem 6 we write G_{n,p} as a union of random graphs with smaller edge probability. So let p_{1} = n^{−1+1/(2k−1)+1/(2k−1)^{2}} and define l to be an integer such that (1 − p_{1})^{l} = 1 − p holds (approximately). Then l = O(n^{1/(2k−1)}). If we let p_{i} = p_{1} for i = 2, …, l, we can write our random graph as G_{n,p} = ⋃_{i=1}^{l} G_{n,p_{i}}. Let H be an edge-maximal C_{2k}-free subgraph of G_{n,p} and define H_{i} = H ∩ G_{n,p_{i}}. Then the following inequalities hold almost surely:

\frac{e(H)}{e(G_{n,p})} ≤ \frac{∑_{i=1}^{l} e(H_{i})}{∑_{i=1}^{l}(e(G_{n,p_{i}}) − ∑_{j=i+1}^{l} e(G_{n,p_{i}} ∩ G_{n,p_{j}}))}

≤ \frac{2 ∑_{i=1}^{l} e(H_{i})}{∑_{i=1}^{l} e(G_{n,p_{i}})}

≤ max_{i} \frac{2e(H_{i})}{e(G_{n,p_{i}})}
= O {(log n)^{1/(2k−1)}n^{−1/(2k−1)^{2}}} .

The second inequality follows from properties of the binomial distribution taking into account that lp_{1} = o(1). The last inequality follows from Theorem 6 because l = O(n^{1/(2k−1)}). □

Using the second part of Lemma 5 we may easily deduce the following theorem, which proves the upper bound of Theorem 2.

Theorem 7 For any δ > 0, there exists a constant C = C(δ) such that, for all p < n^{−1/3−δ}, almost surely

ex(G_{n,p}, C_{4}) ≤ Cn^{4/3}(log n)^{1/3}.  (7)

Proof. For given δ, choose C = max{1/εδ, c_{2}}, where ε and c_{2} are as in Lemma 5. With T = Cn^{4/3}(log n)^{1/3} it follows from Lemma 5 that the expected number of spanning, C_{4}-free subgraphs of G_{n,p} with T edges is

f(\{C_{4}\}, n, T)p^{T} ≤ (\frac{4en^{3}}{T^{2}} e^{δ log n}n^{−1/3−δ})^{T} = (\frac{4e}{(C(log n)^{1/3})^{2}} )^{T} = o(1),

and the result follows. □

3.2 Proof of the lower bounds

The following theorem implies the lower bounds in Theorems 1 and 2.

Theorem 8 For any given integer k ≥ 2, there exists a constant C_{1} = C_{1}(k) > 0 such that if α = α(n) ≥ 1 and p = p(n, α) = αn^{−1+1/(2k−1)} ≤ 1, then almost surely

ex(G_{n,p}, C_{2k}) ≥ C_{1}n^{1+1/(2k−1)}(log α)^{1/(2k−1)}.  (8)

We start by quoting a version of the result of Ajtai, Komlós, Pintz, Spencer, and Szemerédi [1] given by Duke, Lefmann, and Rödl [7]. A hypergraph is called linear if two hyperedges share at most one vertex. As usual, the maximum degree of a hypergraph H is denoted by Δ(H).

Theorem 9 Let r ≥ 1 be an integer and let H be an (r +1)-uniform hypergraph on N vertices. Assume that (i) H is linear, and (ii) Δ(H) ≤ t^{r} for some t ≥ 1. Then H contains an independent set of size at least

c_{r} \frac{N}{t} (log t)^{1/r},

where c_{r} is a constant only depending on r.

Theorem 8 follows easily from Theorem 9.

Proof of Theorem 8. Note that the lower bound stated in the theorem only changes by a multiplicative constant as we change the power of n in α. Hence it is enough to prove the theorem for all α satisfying 1 ≤ α ≤ n^{δ} for some δ > 0. For larger α, the theorem then follows again by monotonicity.

So consider G_{n,p} where p = p(n) = αn^{−1+1/(2k−1)} and α = α(n) ≥ 1. Since e(G_{n,p}) = (1/2 + o(1))αn^{1+1/(2k−1)} almost surely and G_{n,p} almost surely contains at most n^{2k}p^{2k}/(2k) cycles of length 2k, in the sequel we condition on these two events. Define a 2k-uniform hypergraph H on the edge set of G_{n,p} putting 2k edges of G_{n,p} in a hyperedge if they form the edge set of a C_{2k} ⊂ G_{n,p}. The number of hypervertices e ∈ E(G_{n,p}) in H with degree d_{H}(e) larger than 4 × 2k × |E(H)|/|V (H)| ≤ 8n^{2k−2}p^{2k−1} = 8α^{2k−1} is smaller than e(G_{n,p})/4. It is easy to verify that, e.g., for δ < 1/(8k^{2}), if α ≤ n^{δ} then almost surely (*) the number of pairs of hyperedges intersecting in more than one vertex is smaller than e(G_{n,p})/4.

Assume that (*) does hold for our G_{n,p}. Then clearly there is a spanning subgraph G′ ⊂ G_{n,p} such that the corresponding subhypergraph H′ of H on E(G′) is linear, has maximum degree at most 8α^{2k−1}, and has at least (1+o(1))e(G_{n,p})/2 hypervertices (i.e., there are at least (1 + o(1))e(G_{n,p})/2 edges in G′). By Theorem 9, we have that H′ has an independent set of size at least

Ω \{\frac{e(G′)}{2α}(log(2α))^{1/(2k−1)}\} = Ω (n^{1+1/(2k−1)}(log α)^{1/(2k−1)}) ,

concluding the proof of (8). □

3.3 Proof of Lemma 5

This fairly long section is entirely devoted to the proof of Lemma 5. We start with a simple lemma that is used later to show that graphs with large even-girth have a certain expansion property.

Lemma 10 Let H be a graph containing no even cycle of length at most 2k and let v, x, and y be distinct vertices such that x and y are both at distance l < k from v. Then there cannot exist a 2-path in H of the form xzy with z having distance at least l from v.

Proof. Suppose to the contrary that there exists a vertex z as specified in the statement of the lemma. Let x x_{1} … x_{l−1}x_{l} = v and y y_{1} … y_{l−1}y_{l} = v be shortest paths in H from x and respectively y to v. Because z is at distance at least l from v, it has to be different from the vertices on these two paths. If x_{j} is the first vertex from the first path also contained in the second path then the fact that both paths are shortest paths implies that x_{j} = y_{j}. Hence, x x_{1} … x_{j}(= y_{j})y_{j−1} … y_{1}yzx is an even cycle of length 2j + 2 ≤ 2k, which is impossible. □

We may now prove an expansion property of graphs with large even-girth. Given a graph H, a vertex v in H, and an integer l ≥ 1, write Γ′_{l}(v) for the set of vertices of H at distance l from v. Denote by d(v) the degree of the vertex v.

Lemma 11 Let H be a {C_{4}, …, C_{2k}}-free graph with minimal degree d and suppose v is a vertex in H with degree d(v). Then for all integers l ≤ k we have

|Γ′_{l}(v)| ≥ d(v)(d − 2)^{l−1}.

Proof. The case l = 1 is trivially true. Let l < k and suppose that the lemma is true for l. First observe that for a vertex w ∈ Γ′_{l}(v) at least d(w) − 2 of the vertices adjacent to w are at distance l + 1 from v: by Lemma 10 (with z = w) there can be at most one neighbour of w at distance l − 1 from v and at most one neighbour at distance l from v. The remaining, at least d(w) − 2 many, neighbours of w are at distance l + 1 from v.

On the other hand, again by Lemma 10, two such vertices u, w ∈ Γ′_{l}(v) cannot have a common neighbour in Γ′_{l+1}(v). Therefore, |Γ′_{l+1}(v)| ≥ |Γ′_{l}(v)|(d − 2) and the lemma follows by induction. □

Next we prove an upper bound for the number of (2k − 2)-walks that may join two vertices in an L_{k}-free graph G (k ≥ 3). Here we do not attempt to give a best possible result, as any bound that is independent of the number of vertices in our graph G will suffice for our purposes.

Lemma 12 Let k ≥ 3 and the set L_{k} be as defined before Lemma 5. If G is an L_{k}-free graph then for any two vertices x and y in G there are less than (4k)^{8k} different walks of length 2k − 2 from x to y.

Proof. Suppose to the contrary that there are two vertices x and y in G such that there are at least (4k)^{8k} different (2k − 2)-walks from x to y. Let L be the subgraph of G spanned by some (4k)^{8k} of these walks. If L contains e(L) edges then they can form at most e(L)^{2k−2} different (2k − 2)-walks and therefore

e(L) ≥ (4k)^{8k/(2k−2)} > (4k)^{4}.

Now write the edge set of L as a union of the edge sets of (2k − 2)-walks such that no walk is completely contained in the union of the others:

E(L) = ⋃_{i=1}^{l} E_{i},  (9)

where E_{i} is the edge set of the ith walk, and E(L) ≠ ⋃_{j≠i} E_{j} for any i. Obviously l ≥ e(L)/(2k−2) ≥ (4k)^{3}, because every walk can contribute at most 2k−2 new edges to the union in (9).

Let H be the union of some (4k)^{3} walks from x to y. Then H has at most (4k)^{4} vertices. Now, suppose we ‘build’ H by adding one walk at a time. Suppose i ≥ 2 and the ith walk adds y_{i} new edges to H. Then it can add at most y_{i} − 1 new vertices. Observing that y_{i} ≤ 2k − 2, it follows that

\frac{v(H)}{e(H)} ≤ \frac{2 + ∑_{i=1}^{(4k)^{3}}(y_{i} − 1)}{∑_{i=1}^{(4k)^{3}} y_{i}}

≤ \frac{2 + (4k)^{3}(2k − 3)}{(4k)^{3}(2k − 2)}
< 1 − \frac{1}{2k − 1} − \frac{1}{(2k − 1)^{2}} ,

implying that H is a graph from L_{k}, which is impossible. □

The next crucial lemma singles out the key combinatorial idea in the proof of Lemma 5.

Lemma 13 Let integers n ≥ 2, k ≥ 2, T ≥ 1, and 4 ≤ d ≤ 2T/n be fixed. For an integer 4 ≤ t ≤ d, let

ν(t) = ν(n, d, k, t) = (1 − \frac{(d − 3)^{2k−2}}{(4k)^{8k}n} )^{t} + \frac{1}{(d − 3)^{k−1}} .  (10)

Suppose G′ is a {C_{4}, …, C_{2k}} ∪ L_{k}-free graph on n − 1 vertices with T − d edges and minimal degree at least d−1. Then, under the restriction that no even cycle of length at most 2k should arise, there are at most

min_{4≤t≤d} \binom{n}{t}\binom{nν(t)}{d − t}  (11)

ways of adding a new vertex v of degree d to G′.

Proof. Let G′, d, and v be as in the statement of the lemma. Assume for the moment that the neighbourhood Γ(v) of size d of the new vertex v is fixed, and that an integer 0 ≤ t ≤ d is given. Following the ideas of Kleitman and Winston [16] we shall show that (†) for any choice of Γ(v), there exist vertices v_{1}, …, v_{t} in Γ(v) such that the remaining d − t neighbours of v have to be in a set of size at most nν(t).

Roughly speaking, every time a vertex v_{ℓ} from the neighbourhood of v is chosen, certain other vertices become “forbidden” as neighbours of v, since joining v to both v_{ℓ} and a “forbidden” vertex creates an even cycle of length at most 2k. It is clear that assertion (†) proves Lemma 13.

We now prove (†). Thus let Γ(v) be fixed, and assume that the neighbours v_{1}, …, v_{ℓ} (0 ≤ ℓ < t) have already been found. Denote by Z_{ℓ} the set of eligible vertices for v_{ℓ+1}, namely, the ones that have not been forbidden by v_{1}, …, v_{ℓ}. Note that Z_{0} is by definition the whole vertex set of G′. Set

ζ_{ℓ} = |Z_{ℓ}|.

Call a (2k−2)-walk x_{0}x_{1} … x_{2k−2} a composed walk if x_{0} ≠ x_{2k−2} and x_{0} … x_{k−1} and x_{k−1} … x_{2k−2} are shortest paths in G.

Now we order Z_{ℓ} and then select v_{ℓ+1} from among the elements of Z_{ℓ} in such a way that many vertices will then be forbidden: let z_{1}^{(ℓ)} be a vertex from Z_{ℓ} joined to the greatest number of vertices of Z_{ℓ} by a composed walk, and inductively define z_{j}^{(ℓ)} for 2 ≤ j ≤ |Z_{ℓ}| to be a vertex from Z_{ℓ} \ {z_{1}^{(ℓ)}, …, z_{j−1}^{(ℓ)}} joined to the greatest number of vertices of this set by a composed walk. If i is the smallest index such that z_{i}^{(ℓ)} is in the neighbourhood Γ(v) of v, then define v_{ℓ+1} to be z_{i}^{(ℓ)}. Furthermore, set

X = Z_{ℓ}\{z_{1}^{(ℓ)}, …, z_{i}^{(ℓ)}}, ξ = |X|, and Z_{ℓ+1} = X \ ⋃_{j=1}^{k−1} Γ̃_{2j}(v_{ℓ+1}),

where Γ̃_{2j}(v_{ℓ+1}) is the set of vertices that can be reached from v_{ℓ+1} by a path of length 2j.

In order to obtain an upper bound for ζ_{ℓ+1} = |Z_{ℓ+1}|, we first estimate the number of composed walks whose starting and end points are in X. For a vertex u ∈ V (G′), let q_{u} denote the number of vertices in X at distance k − 1 from u. By Lemma 11,

∑_{u∈V (G′)} q_{u} = ∑_{x∈X} |Γ′_{k−1}(x)| ≥ ξ(d − 3)^{k−1}.

Putting together two shortest paths of length k − 1 starting at the same vertex u ∈ V (G′) and ending at some pair of distinct vertices of X yields a composed walk. Therefore the number of such walks is at least

∑_{u∈V (G′)} \binom{q_{u}}{2} ≥ (n − 1)\binom{ξ(d − 3)^{k−1}/(n − 1)}{2}

= \frac{ξ(d − 3)^{k−1}}{2} (\frac{ξ(d − 3)^{k−1}}{n − 1} − 1) .

By the definition of v_{ℓ+1}, there are at least

\frac{2}{ξ} ∑_{u∈V (G′)} \binom{q_{u}}{2} ≥ (d − 3)^{k−1} (\frac{ξ(d − 3)^{k−1}}{n − 1} − 1)

composed walks starting from v_{ℓ+1}.

If v_{ℓ+1}y_{1} … y_{k−1}(= y′_{k−1})y′_{k−2} … y′_{1}x is a composed walk, then x cannot be a neighbour of v: this is because such a walk is composed of two shortest paths and if y_{j} is the first vertex from the first path occurring also in the second path then y_{j} = y′_{j}. Hence there is a path of length 2j between v_{ℓ+1} and x and an edge between x and v would complete a cycle of length 2j + 2 ≤ 2k, which is not allowed.

For k ≥ 3, by Lemma 12, at most (4k)^{8k} composed walks can start at v_{ℓ+1} and end at x, for any vertex x. For k = 2, no two composed walks starting at v_{ℓ+1} can have the same endvertex, for otherwise a C_{4} would arise. Therefore, there are at least

\frac{(d − 3)^{k−1}}{(4k)^{8k}} (\frac{ξ(d − 3)^{k−1}}{n − 1} − 1)  (12)

vertices in X which can be reached from v_{ℓ+1} by a composed walk. These vertices cannot share an edge with v and hence

ζ_{ℓ+1} ≤ ξ − \frac{(d − 3)^{k−1}}{(4k)^{8k}} (\frac{ξ(d − 3)^{k−1}}{n − 1} − 1)
≤ ξ (1 − \frac{(d − 3)^{2k−2}}{(4k)^{8k}(n − 1)}) + \frac{(d − 3)^{k−1}}{(4k)^{8k}}
≤ ζ_{ℓ} (1 − \frac{(d − 3)^{2k−2}}{(4k)^{8k}n} ) + \frac{(d − 3)^{k−1}}{(4k)^{8k}} .

Using that ζ_{0} = n − 1, it follows by induction that

ζ_{ℓ} ≤ n (1 − \frac{(d − 3)^{2k−2}}{(4k)^{8k}n} )^{ℓ} + \frac{n}{(d − 3)^{k−1}} = nν(ℓ).

Thus (†) follows. As observed above, Lemma 13 follows from (†). □

We are now in position to prove Lemma 5.

Proof of Lemma 5. We shall prove Lemma 5 by applying Lemma 13 recursively. Given a {C_{4}, …, C_{2k}} ∪ L_{k}-free graph G on n vertices, let v_{n} be a vertex of minimal degree. Remove it and let v_{n−1} be a vertex of minimal degree in the remaining graph, and so on. For simplicity, let d_{i} denote the degree of v_{i} in the graph G \ {v_{i+1}, …, v_{n}}. Then by a recursive application of Lemma 13 we obtain

f(\{C_{4}, …, C_{2k}\} ∪ L_{k}, n, T) ≤ ∑_{(d_{i})} \{n!n^{3n} ∏_{i=1}^{n} [ min_{4≤t≤d_{i}} \binom{n}{t}\binom{nν(n, d_{i}, k, t)}{d_{i} − t}]\} .

(13)

Here,

ν(n, d_{i}, k, t) = (1 − \frac{(d_{i} − 3)^{2k−2}}{(4k)^{8k}n} )^{t} + \frac{1}{(d_{i} − 3)^{k−1}}

is as defined in Lemma 13, the sum is over all non-negative integer vectors (d_{i})_{1≤i≤n} such that d_{1} + … + d_{n} = T, and the minimum is defined to be 1 if d_{i} ≤ 3. Note that the factor of n! takes care of all the possible orderings v_{1}, …, v_{n} of the vertices of G. The factor n^{3n} takes care of all the indices i such that d_{i} ≤ 3. Indeed, for any such i, the number of ways v_{i} can be added to G \ \{v_{i}, …, v_{n}\} is trivially bounded by \binom{n}{3} ≤ n^{3}.

Our task for the remainder of the proof is to massage (13) to deduce Lemma 5. Unfortunately, this will entail some fussy and somewhat tedious calculations.

Before we start, observe that for “small” d_{i}, the first term in ν(n, d_{i}, k, t) is the larger one, whereas for “large” d_{i} the second term dominates. To be able to distinguish between these two cases, we introduce a value d_{0} for which both terms are roughly equal at t = d_{0}/2. More precisely, let d_{0} ≥ 4 be such that

\frac{d_{0}^{2k−1}}{2(8k)^{8k}n} = (k − 1) log(d_{0} − 3).  (14)

Note that the order of magnitude of d_{0} is (n log n)^{1/(2k−1)}. More precisely, for n sufficiently large we have

c_{2}(n log n)^{1/(2k−1)} ≤ d_{0} ≤ (8k)^{8}(n log n)^{1/(2k−1)},

where c_{2} is as in the statement of Lemma 5. Now define (for each n) the functions

g_{1}(x) = \frac{2x^{2k}}{(8k)^{8k+1}n}

and

g_{2}(x) = (k −1)x log x− \frac{1}{2}kd_{0} log x− \frac{d_{0}}{2} ((k − 2) log d_{0} − (1 − \frac{1}{k} ) log(d_{0} − 3)),

and let

g(x) = \{ \begin{matrix}g_{1}(x) & if 1 ≤ x < d_{0} \\ g_{2}(x) & if d_{0} ≤ x. \end{matrix}

We claim that for all 1 ≤ d ≤ n we have

min_{4≤t≤d} \binom{n}{t}\binom{nν(n, d, k, t)}{d − t} ≤ (\frac{4en}{d})^{d} e^{−g(d)},  (15)

where ν(n, d, k, t) is as in (10) and the minimum is defined to be 1 for d ≤ 3.

¿¿From inequality (15) the proof of Lemma 5 is easily concluded: the only missing observation is that the function g is convex. This is obviously true for g_{1} and g_{2}. So the only interesting case is the point x = d_{0}. Here it suffices to check that g_{1}(d_{0}) = g_{2}(d_{0}) and g′_{1}(d_{0}) ≤ g′_{2}(d_{0}). This is easily verified using (14).

The convexity of g and Jensen’s inequality imply that

f(\{C_{4}, …, C_{2k}\} ∪ L_{k}, n, T) ≤ n^{4n} ∑ ∏ (\frac{4en}{d_{i}})^{d_{i}} e^{−g(d_{i})}

≤ n^{5n} (\frac{4en^{2}}{T} )^{T} e^{−ng(T/n)},  (16)

where the sum is over all vectors (d_{i})_{i=1}^{n} of non-negative integers d_{i} with d_{1} + … + d_{n} = T, and the product is over all 1 ≤ i ≤ n with d_{i} ≥ 4. The statement of the lemma is easily deduced from (16) by distinguishing two cases according to the size of T/n.

Now we go back to the proof of inequality (15). The cases d = 1, 2, and 3 are easily checked. For d ≥ 4 we first observe that, from the definition (10) of ν, we have

nν(n, d, k, t) ≤ 2n max \{exp (−\frac{d^{2k−2}t}{(8k)^{8k}n}) , (d − 3)^{−(k−1)}\} .  (17)

Consider first the case in which d < d_{0}. Here we set t = ⌊d/2⌋. By the choice of d_{0}, the maximum in (17) is attained by the first term. Therefore,

\binom{n}{t}\binom{nν(n, d, k, t)}{d − t} ≤ \binom{n}{⌊d/2⌋}\binom{2n exp \{−d^{2k−1} /(4(8k)^{8k}n)\}}{⌈d/2⌉}

≤ (\frac{en}{⌊d/2⌋})^{⌊d/2⌋} (\frac{2en exp \{−d^{2k−1} /(4(8k)^{8k}n)\}}{⌈d/2⌉})^{⌈d/2⌉}

≤ (\frac{4en}{d})^{⌊d/2⌋} (\frac{4en}{d} exp \{−d^{2k−1} /(4(8k)^{8k}n)\})^{⌈d/2⌉}

≤ (\frac{4en}{d})^{d} exp \{−\frac{2d^{2k}}{(8k)^{8k+1}n}\} .

We now turn to the case d ≥ d_{0}. Here we use t = ⌈d_{0}/2⌉. Then the maximum in (17) is attained by the second term (this follows from (14)). Hence,

\binom{n}{t}\binom{nν(n, d, k, t)}{d − t} ≤ \binom{n}{⌈d_{0}/2⌉}\binom{2n/(d − 3)^{k−1}}{d − ⌈d_{0}/2⌉}

≤ (\frac{en}{⌈d_{0}/2⌉})^{⌈d_{0}/2⌉} (\frac{2en}{d^{k−1}(d − ⌈d_{0}/2⌉)})^{d−⌈d_{0}/2⌉} (\frac{d}{d − 3})^{(k−1)(d−⌈d_{0}/2⌉)}

≤ (\frac{4en}{d})^{d} d^{d}2^{−d}d_{0}^{−d_{0}/2} (\frac{1}{d^{k−1}(d − ⌈d_{0}/2⌉)})^{d−⌈d_{0}/2⌉} e^{3k}

≤ (\frac{4en}{d})^{d} 2^{−d}d_{0}^{−d_{0}/2}d^{d−(k−1)d+kd_{0}/2−⌈d_{0}/2⌉+k−1} (\frac{2}{d})^{d−⌈d_{0}/2⌉} e^{2+3k}

≤ (\frac{4en}{d})^{d} d^{−(k−1)d+kd_{0}/2},

completing the proof of inequality (15). Lemma 5 is therefore proved. □

4 Proof of Theorem 4

We start by stating Lemma 14, which will enable us to prove Theorem 4. To state our lemma, let h_{k}(n, d) be the number of n-vertex graphs with minimal degree at least d and even-girth greater than 2k.

Lemma 14 Let k ≥ 2 be an integer. Then there is a constant c_{3} = c_{3}(k) > 0 depending only on k such that, for all integers d ≥ 4 and all sufficiently large n, we have

h_{k}(n, d) ≤ nh_{k}(n − 1, d − 1) min_{4≤t≤d} \binom{n}{t}\binom{nμ(t)}{d − t},

where

μ(t) = μ(n, d, k, t) = (1 − \frac{(d − 3)^{k(k−1)}}{c_{3}n^{k−1}} )^{t} + \frac{1}{(d − 3)^{k−1}} .  (18)

We now prove Theorem 4 assuming Lemma 14.

Proof of Theorem 4. To prove the theorem, it is enough to show that there exists a constant n_{0} such that, for all n ≥ n_{0}, we have

log \frac{|Forb_{n}(C_{4}, …, C_{2k})|}{|Forb_{n−1}(C_{4}, …, C_{2k})|} ≤ (log 2)c_{k}n^{1/k}.  (19)

Any {C_{4}, …, C_{2k}}-free graph on n vertices with minimal degree d may be obtained from a {C_{4}, …, C_{2k}}-free graph on n − 1 vertices and minimal degree at least d − 1 by the addition of a vertex of degree d. For d ≤ c_{k}n^{1/k}/ log n, inequality (19) follows from the fact that log \{n\binom{n}{d}\} ≤ c_{k}n^{1/k} for any sufficiently large n.

So let us from now on assume that d ≥ c_{k}n^{1/k}/ log n. With

t_{0} = ⌈\frac{c_{3}n^{k−1} log n}{(d − 3)^{k(k−1)}} ⌉ = O \{(log n)^{k(k−1)+1}\} ,

Lemma 14 yields that

log \frac{|Forb_{n}(C_{4}, …, C_{2k})|}{|Forb_{n−1}(C_{4}, …, C_{2k})|} < log (n\binom{n}{t_{0}}\binom{nμ(n, d, k, t_{0})}{d − t_{0}})
≤ log (n^{1+t_{0}} \binom{t_{0} + 1 + n/(d − 3)^{k−1}}{d})
= (1 + t_{0}) log n + (1 + o(1)) log \binom{n/d^{k−1}}{d}.

As (1 + t_{0}) log n = o(n^{1/k}), we only need to estimate the second term. With x = dn^{−1/k}, using Stirling’s formula one sees that

log \binom{n/d^{k−1}}{d} ≤ (\frac{−1}{x^{k−1}} \{(1 − x^{k}) log(1 − x^{k}) + x^{k} log x^{k}\}) n^{1/k}.

The first factor is easily seen to be smaller than (log 2)(0.531k + 1.45) (e.g., by considering the Taylor series of this function). Hence Theorem 4 is proven.

□

It now remains to prove Lemma 14. One may prove this lemma following the proof of Lemma 13, and suitably altering a step in that proof.

Proof of Lemma 14 (Sketch). Only once in the proof of Lemma 13 is it needed that the graphs under consideration are L_{k}-free, namely, in the derivation of inequality (12), where Lemma 12 is applied to give an upper bound for the number of composed walks of length 2k − 2 between two vertices. To show an analogue of Lemma 12, fix two distinct vertices x and y in a {C_{4}, …, C_{2k}}-free graph G with maximal degree Δ = Δ(G). We shall prove that (‡) there is a constant c_{3} = c_{3}(k) such that the number of different (2k−2)-walks from x to y in G is at most c_{3}Δ^{k−2}.

Denote by d(x, y) the distance between the vertices x and y in G. We first consider the case in which d(x, y) ≥ k. To construct a (2k − 2)-walk (x = )x_{0}x_{1} … x_{2k−2}(= y) in G, choose first k indices 0 ≤ i_{1} < … < i_{k} ≤ 2k − 3 such that

k ≥ d(x_{i_{ρ}}, y) = d(x_{i_{ρ}+1}, y) + 1 for ρ = 1, …, k.

Observe that by Lemma 10 (with z = x_{i_{ρ}}), the vertex x_{i_{ρ}+1} is uniquely determined once x_{i_{ρ}} is chosen. For an index j not among these k indices, there are at most Δ choices for x_{j+1} for a given vertex x_{j}. Hence, in total, there are at most

\binom{2k − 2}{k}Δ^{k−2}

(2k − 2)-walks from x to y.

For the case when d(x, y) < k one has to use in addition that, again by Lemma 10, for a given x_{j}, there is only one choice for x_{j+1} if d(x_{j}, y) = d(x_{j+1}, y) < k. The number of walks containing a vertex x_{j} with d(x_{j}, y) ≥ k is estimated as in the first case. For the other walks, partition the index set {0, 1, …, 2k − 3} into three sets A, B, and C such that

d(x_{i_{ρ}}, y) = d(x_{i_{ρ}+1}, y) − 1  for ρ ∈ A,
d(x_{j_{ρ}}, y) = d(x_{j_{ρ}+1}, y)  for ρ ∈ B,
d(x_{m_{ρ}}, y) = d(x_{m_{ρ}+1}, y) + 1 for ρ ∈ C.

Then, |C| − |A| = d(x, y) ≥ 1 and, consequently, |A| ≤ |C| − 1 ≤ k − 2. Hence, the number of all (2k − 2)-walks from x to y in the second case is bounded from above by

\binom{2k − 2}{k}Δ^{k−2} + ∑ \binom{2k − 2}{a, b, c}Δ^{a} ≤ c_{3}Δ^{k−2},

where the sum is over all triples (a, b, c) of non-negative integers with a + b + c = 2k − 2 and a ≤ k − 2, and c_{3} = c_{3}(k) is a suitably chosen constant. Thus (‡) follows. Actually, it would have been enough to bound from above the number of composed walks between two vertices, but this is not much easier than bounding the number of (2k − 2)-walks.

To apply (‡), we use that Δ ≤ n/(d − 3)^{k−1}, which follows immediately from Lemma 11. Following the notation of Lemma 13, we have shown (instead of (12)) that there are at least

\frac{(d − 3)^{k−1}}{c_{3}Δ^{k−2}} (\frac{ξ(d − 3)^{k−1}}{n − 1} − 1) ≥ \frac{(d − 3)^{(k−1)^{2}}}{c_{3}n^{k−2}} (\frac{ξ(d − 3)^{k−1}}{n − 1} − 1)

vertices in X that can be reached from v_{ℓ+1} by a composed walk. With this modification, Lemma 14 may now be proven in the same way as Lemma 13.

□

In order to prove (5), i.e., to get rid of the smaller cycles, one could make use of an analogue to Lemma 11 as proven in [6], where only C_{2k} is forbidden. However composed walks that are not self-avoiding are useless now and substantially new ideas would be needed in order to prove that sufficiently many composed walks are not self-avoiding.

5 Concluding remarks

In the case in which p = p(n) is such that pn^{−1+1/(2k−1)} = O(1) and pn → ∞, we may actually determine ex(G_{n,p}, C_{2k}) more precisely as follows. Clearly,

ν_{2k}(G_{n,p}) ≤ e(G_{n,p}) − ex(G_{n,p}, C_{2k}) ≤ 2kν_{2k}(G_{n,p}),  (20)

where ν_{2k}(G_{n,p}) denotes the maximal size of a pairwise edge-disjoint family of copies of C_{2k} in G_{n,p}. For this range of p by Theorem 4 from [19] (or more precisely, by the remarks to this theorem), we almost surely have

ν_{2k}(G_{n,p}) ≍ n^{2k}p^{2k}.  (21)

Inequalities (20) and (21) determine e(G_{n,p})−ex(G_{n,p}, C_{2k}) up to a multiplicative constant.

It would not be hard to weaken the upper bound on α = α(n) in Theorem 1 very slightly. Here is how: one could allow a larger constant in the statement of Lemma 12 and then L_{k} could be defined slightly differently. However, with these small changes our arguments give (4) for α = α(n) up to n^{1/(2k−1)(2k−2)−o(1)} only.

It would be very interesting to determine ex(G_{n,p}, C_{2k}) up to a constant factor for a much wider range of p = p(n) than the one given in Theorem 1. We have no guess as to the behaviour of ex(G_{n,p}, C_{2k}) for reasonably large p = p(n). For this case we only know Corollary 3 and the trivial inequalities

(1 + o(1))p ex(n, C_{2k}) ≤ ex(G_{n,p}, C_{2k}) ≤ ex(n, C_{2k}).

The case p constant and k = 2 is already mentioned as an open problem in Babai, Simonovits, and Spencer [2].

Acknowledgement

We are grateful to Z. Füredi for informing us about the results of D.J. Kleitman and D.B. Wilson, and to these authors for letting us have a preliminary copy of [15].

This paper went through a detailed revision owing to the insightful comments of two anonymous referees. We are glad to thank them for their fine job.

References

[1] M. Ajtai, J. Komlós, J. Pintz, J. Spencer, and E. Szemerédi. Extremal uncrowded hypergraphs. J. Combinatorial Theory, Series A, 32:321–335, 1982.

[2] L. Babai, M. Simonovits, and J. Spencer. Extremal subgraphs of random graphs. J. Graph Theory, 14:599–622, 1990.

[3] C.T. Benson. Minimal regular graphs of girths eight and twelve. Canad. J. Math., 18:1091–1094, 1966.

[4] B. Bollobás. Extremal Graph Theory. Academic Press, London, 1978.

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

[6] J.A. Bondy and M. Simonovits. Cycles of even length in graphs. Journal of Combinatorial Theory, Series B, 16:97–105, 1974.

[7] R.A. Duke, H. Lefmann, and V. Rödl. On uncrowded hypergraphs. Random Structures and Algorithms, 6(2–3):209–212, 1995.

[8] P. Erdős. Some of my old and new combinatorial problems. In B. Korte, L. Lovász, H.J. Prömel, and A. Schrijver, editors, Paths, Flows, and VLSI-Layout, pages 35–45. Springer-Verlag, Berlin, Heidelberg, 1990.

[9] P. Erdős and R.J. Faudree. Problem presented at Kolloquium über Kombinatorik. Bielefeld, Germany, November 1990.

[10] P. Erdős and M. Simonovits. Compactness results in extremal graph theory. Combinatorica, 2(3):275–288, 1982.

[11] P. Frankl and Z. Füredi. Exact solution of some Turán-type problems. J. Combinatorial Theory, Series A, 45:226–262, 1987.

[12] Z. Füredi. Random Ramsey graphs for the four-cycle. Discrete Mathematics, 126:407–410, 1994.

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

[14] P.E. Haxell, Y. Kohayakawa, and T. Łuczak. Turán’s extremal problem in random graphs: forbidding odd cycles. Combinatorica, 16(1):107–122, 1996.

[15] D.J. Kleitman and D.B. Wilson. On the number of graphs which lack small cycles. Manuscript, 1994; accepted for publication in Discrete Mathematics.

[16] D.J. Kleitman and K.J. Winston. On the number of graphs without 4-cycles. Discrete Mathematics, 41:167–172, 1982.

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

[18] B. Kreuter. Extremale und Asymptotische Graphentheorie für verbotene bipartite Untergraphen. Diplomarbeit, Forschungsinstitut für Diskrete Mathematik, Universität Bonn, January 1994.

[19] B. Kreuter. Threshold functions for asymmetric Ramsey properties with respect to vertex colorings. Random Structures and Algorithms, 9(3):335–348, 1996.

[20] M. Simonovits. Extremal graph theory. In L.W. Beineke and R.J. Wilson, editors, Selected Topics in Graph Theory, volume 2, pages 161–200. Academic Press, London, 1983.

[21] A. Steger. Asymptotic Properties of H-free Graphs. Habilitationsschrift, Forschungsinstitut für Diskrete Mathematik, Universität Bonn, November 1993.

[22] R. Wenger. Extremal graphs with no C^{4}’s, C^{6}’s, or C^{10}’s. Journal of Combinatorial Theory, Series B, 52:113–116, 1991.