The Turán Number for the Hexagon

Assaf Naor Jacques Verstraëte

Microsoft Research One Microsoft Way Redmond, WA 98052-6399

Abstract

It is shown that the maximal number of edges in an n-vertex graph containing no cycle of length six has order of magnitude \frac{1}{2}n^{4/3}.

1 Introduction

The forbidden subgraph problem, commonly known as a Turán-type problem, involves the determination of the maximum number of edges that an n-vertex graph may have if it contains no isomorphic copy of a fixed graph H. This number is called the Turán number for H, and denoted t(n, H). Apart from its intrinsic interest, this type of problem has drawn considerable attention since the early 1940s because many graphs arising from natural algebraic constructions (for example, Cayley graphs and incidence graphs of projective geometries) are known not to contain certain subgraphs. The case of the complete graph K_{r} was studied by Turán in [20], where it was shown that:

t(n, K_{r}) = ∑_{1≤i<j≤r−1} ⌊\frac{n + i − 1}{r − 1}⌋ · ⌊\frac{n + j − 1}{r − 1}⌋

Here, and in what follows, the notation a_{n} ∼ b_{n} is used as shorthand for the statement lim_{n→∞} a_{n}/b_{n} = 1. In words, we say that a_{n} has order of magnitude b_{n}.

When the forbidden subgraph H is not bipartite, the Turán problem is well understood. The Erdős-Simonovits-Stone Theorem [8] asserts that as long as H is not bipartite,

t(n, H) ∼ (1 − \frac{1}{χ − 1}) \binom{n}{2},

where χ is the chromatic number of H. Simonovits [19] further showed that if the chromatic number of H decreases under deletion of any edge of H, and n is sufficiently large, then t(n, H) = t(n, K_{χ}), generalizing Turán’s Theorem.

When the forbidden subgraph H is bipartite, much less is known. Kövari, Sós and Turán [13] showed that for the complete bipartite graph K_{r,s} with r ≤ s, t(n, K_{r,s}) = O(n^{2−1/r}), and therefore, for each bipartite graph H, there is a constant c > 0 such that t(n, H) = O(n^{2−c}). Erdős and Simonovits [9] conjectured that for every bipartite graph H there are positive constants a, α such that t(n, H) ∼ an^{1+α}. In particular, it has been a major long-standing open problem in combinatorics to estimate the maximum size of a graph on n vertices containing no cycle of length 2k, or 2k-gon. Such a cycle is denoted by C_{2k}. The order of magnitude of t(n, C_{2k}) is not known for any integer k > 2. In the case k = 2, it was proved independently by Reiman [17], Brown [5] and Erdős, Rényi and Sós [7] that t(n, C_{4}) ∼ \frac{1}{2}n^{3/2}. Füredi [11] showed that for any prime power q > 13,

t(q^{2} + q + 1, C_{4}) = \frac{q(q + 1)^{2}}{2} .

In fact, Füredi characterized in [10] the unique extremal graph on q^{2} + q + 1 vertices which achieves the above equality.

This paper settles the next unknown case, namely k = 3. We establish the order of magnitude of t(n, C_{6}), the Turán Number for the hexagon, thereby answering affirmatively a question posed by Erdős and Simonovits in [9]:

Theorem 1.1 The Turán Number for the hexagon has order of magnitude \frac{1}{2}n^{4/3}.

By considering polarities in certain rank two geometries, Lazebnik, Ustimenko and Woldar [15] constructed, for every prime power q, a graph on q^{3} + q^{2} + q + 1 vertices with \frac{1}{2}(q + 1)(q^{3} + q^{2} + q + 1) − \frac{1}{2}(q^{2} + 1) edges, and which contains no hexagon. In other words, for infinitely many n,

t(n, C_{6}) ≥ \frac{1}{2}n^{4/3} + \frac{1}{3}n + O(n^{2/3}).

It is known that for some θ < 1 and every sufficiently large integer n, there is a prime in the interval [n − n^{θ}, n] (for example, a recent result of Baker, Harman and Pintz [1] shows we can take θ = 21/40). A straightforward calculation now shows the construction mentioned above implies, for all n, that

t(n, C_{6}) ≥ \frac{1}{2}n^{4/3} − O(n^{1+θ/3}).

Therefore, in order to prove Theorem 1.1 it suffices to show that t(n, C_{6}) ≤ \frac{1}{2}n^{4/3} + o(n^{4/3}). We prove that:

t(n, C_{6}) ≤ \frac{1}{2}n^{4/3} + O(n^{10/9}).

The best known result prior to Theorem 1.1 is due to Füredi [12], who proved that t(n, C_{6}) ≤ 0.532n^{4/3} − o(n^{4/3}). The only other value of k for which t(n, C_{2k}) is known up to a constant factor is k = 5 (a simplification of the original construction, due to Benson [2], may be found in Wenger [22]). In the current state of knowledge, the best known bounds for t(n, C_{2k}) valid for all k ≥ 2 are cn^{1+2/(3k)} from below for some positive constant c, via constructions due to Lazebnik, Ustimenko and Woldar [15], and 8(k − 1)n^{1+1/k} from above by Verstraëte [21]. We refer to the survey [4] for an exposition of related problems and results in extremal graph theory.

In [9], Erdős and Simonovits conjectured that for every integer k ≥ 3, t(n, C_{2k}) ∼ \frac{1}{2}n^{1+ \frac{1}{k}}. The present article shows that this is indeed the case for k = 3, while the case k = 5 was disproved in [14]. The case k = 4 seems to be a challenging problem. We believe that our methods yield interesting bounds for other values of k, but we chose to present a self-contained exposition of the complete solution of the case k = 3. The discussion of other applications and generalizations of our approach is deferred to a second paper on the same topic.

2 A Regularization Lemma

In this section, we present the a key lemma in the proof of Theorem 1.1. This lemma, which may be referred to as a regularization lemma, implies that the Turán number for the hexagon is of the same order of magnitude as the maximum number of edges in an almost regular n-vertex hexagon-free graph. To prove this result, we require the following proposition, the first part of which is due to Sárkőzy [18] when c = 180. We improve this result in [16], by replacing the constant c with the optimal constant c = 1. The second part of the the proposition below is well known (see for example [21]).

Proposition 2.1 If H is an m×n hexagon-free bipartite graph then, for some absolute constant c ≥ 1,

e(H) ≤ c[(mn)^{2/3} + n].

Furthermore, for all n, t(n, C_{6}) ≤ cn^{4/3}.

The following terminology is required: a spanning subgraph of a graph G on vertex set V is a subgraph of G containing all vertices of V. For sets S, T ⊂ V, e(S, T) denotes the number of edges with one vertex in S and one in T. The number of edges in G, denoted e(G), is sometimes referred to as the size of G. We write d(v) for the number of edges containing v. We now proceed to the regularization lemma:

Lemma 2.2 Let G = (V, E) be an n-vertex hexagon-free graph. Then for every positive Δ < n^{1/2}, G contains a spanning subgraph of maximum degree at most Δ and size at least:

e(G) − (6c)^{3} (\frac{n}{Δ})^{2} ,

where c is as in Proposition 2.1.

Proof. For each t, let S_{t} = \{v ∈ G : d(v) ≥ t\}. We will show, for t ≤ \sqrt{n}, that |S_{t}| ≤ (4c)^{3}n^{2}/t^{3}. This is clearly true if t ≤ 4c|S_{t}|^{1/3}, so we assume t ≥ 4c|S_{t}|^{1/3}. Now, by the second assertion in Proposition 2.1, the number of edges in S_{t} is at most c|S_{t}|^{4/3}. Therefore

e(S_{t}, V \ S_{t}) ≥ |S_{t}|t − c|S_{t}|^{4/3} ≥ \frac{1}{2}|S_{t}|t.

On the other hand, by Proposition 2.1,

e(S_{t}, V \ S_{t}) ≤ c|S_{t}|^{2/3}n^{2/3} + cn.

Comparing these bounds, we obtain |S_{t}| ≤ (4c)n/t or |S_{t}| ≤ (4c)^{3} \frac{n^{2}}{t^{3}} . For t ≤ ⌊\sqrt{n}⌋, therefore, |S_{t}| ≤ (4c)^{3}n^{2}/t^{3}. Let S = S_{⌊\sqrt{n}⌋+1}. Then, as above, e(S, S) ≤ c|S|^{4/3} and:

e(S, V \S) ≥ |S|(⌊\sqrt{n}⌋ − c|S|^{1/3}) ≥ |S|\sqrt{n} − 2c|S|^{2/3}n^{2/3}.

Applying Proposition 2.1, we also find

e(S, V \S) ≤ c(|S|n)^{2/3} + cn.

A routine calculation now shows that |S| < (6c)^{3}\sqrt{n}. Hence the total number of edges induced by S in G satisfies:

e(S, S) + e(S, V \S) ≤ c|S|^{4/3} + c(|S|n)^{2/3} + cn ≤ \frac{1}{2}(6c)^{3}n ≤ \frac{(6c)^{3}n^{2}}{2Δ^{2}} .

We now greedily delete edges from G. First delete the edges incident with at least one vertex of S. Then start with the set of vertices of G of degree ⌊\sqrt{n}⌋, and delete one edge per vertex of this set. In general, having reached a subgraph of G of maximum degree t < \sqrt{n}, delete one edge per vertex of degree t in this subgraph of G. Continuing this procedure ⌊\sqrt{n}⌋ − Δ steps, we obtain a spanning subgraph G̃ of G, of maximum degree at most Δ and

e(G̃) ≥ e(G) − ∑_{t=Δ+1}^{⌊\sqrt{n}⌋} |S_{t}| − \frac{(6c)^{3}n^{2}}{2Δ^{2}}
≥ e(G) − ∑_{t=Δ+1}^{n} \frac{(4c)^{3}n^{2}}{t^{3}} − \frac{(6c)^{3}n^{2}}{2Δ^{2}}
≥ e(G) − ∫_{Δ}^{∞} \frac{(4c)^{3}n^{2}}{t^{3}} dt − \frac{(6c)^{3}n^{2}}{2Δ^{2}} ≥ e(G) − \frac{(6c)^{3}n^{2}}{Δ^{2}} .

3 Small Subgraphs

In this section, we analyze the interaction between certain dense subgraphs of a hexagonfree graph G, namely triangles and complete bipartite graphs. We will conclude, in a sense made precise later, that there are few triangles and complete bipartite subgraphs K_{2,t} in a hexagon-free graph. Some further notation is required first. A path (or cycle) in a graph G is represented by a sequence of vertices, for example, (v_{1}, v_{2}, v_{3}) denotes a path of length three. For t ≥ 2, we call a complete bipartite graph K_{2,t} ⊂ G maximal if it is not properly contained in any other complete bipartite subgraph of G. The set of all maximal complete bipartite subgraphs of a graph G is denoted B(G).

Lemma 3.1 The number of maximal complete bipartite subgraphs of a hexagon-free graph G, containing an edge e, is at most eleven. In particular,

∑_{K∈B(G)} e(K) ≤ 11e(G).

Proof. Let G_{1}, G_{2}, …, G_{k} be maximal complete bipartite subgraphs of G. The number of complete bipartite subgraphs of K_{5}, the complete graph on five vertices, containing a fixed edge of K_{5}, is exactly nine. It is therefore sufficient to show that for some set S of at most two integers,

|⋃_{t∉S} V (G_{t})| ≤ 5.

Indeed, it then follows that k ≤ 11. We first observe that since G doesn’t contain a hexagon, for any two quadrilaterals Q_{i} ⊂ G_{i} and Q_{j} ⊂ G_{j}, both containing e, |V (Q_{i}) ∩ V (Q_{j})| ≥ 3, otherwise the edges of Q_{i} ∪ Q_{j} distinct from e form a hexagon. There are now three possibilities:

(1) For all i, j, Q_{i} ∪ Q_{j} ≅ K_{2,3}
(2) There exist i, j such that Q_{i} ∪ Q_{j} ≅ K_{4}, or

(3) There exist i, j such that Q_{i} ∪ Q_{j} consists of a pentagon, C, and two diagonals incident at some vertex v ∈ V (C).

Let A_{i} and B_{i} denote the parts in the complete bipartite graph G_{i}, with |A_{i}| ≥ |B_{i}| = 2. Suppose (1) holds. By the maximality of G_{i} and G_{j}, we necessarily have that |A_{i}| ≥ 3 and |A_{j}| ≥ 3. For the same reason, B_{j} ⊂ A_{i}, otherwise G_{i} is contained in a complete bipartite graph with parts A_{i} ∪ B_{j} and B_{i}. By the maximality of G_{j}, A_{j} ≠ B_{i}. If A_{j}\(A_{i} ∪ B_{i}) ≠ ∅, then there is a hexagon containing a vertex of A_{j}\(A_{i} ∪ B_{i}) ≠ ∅, the edge e, and all of B_{i}. Therefore

A_{j}\(A_{i} ∪ B_{i}) = ∅.

As A_{j} ≠ B_{i}, there is a vertex v ∈ A_{i} ∩ A_{j}, adjacent to all of B_{j}. If |A_{i}| ≥ 4, then we find a hexagon containing v, all of B_{i}, all of B_{j} and any vertex of A_{i}\({v} ∪ B_{j}). Therefore |A_{i}| = |A_{j}| = 3, V (G_{i}) = V (G_{j}), and |V (G_{i})| = |V (G_{j})| = 5. As this holds for all i, j, we are done. So we assume that for some i, j, (2) or (3) holds.

Suppose (3) holds for some i, j, and e = {b, c}. Then we may write C = (v, a, b, c, d, v), where Q_{i} = (v, a, b, c, v) and Q_{j} = (v, b, c, d, v). If u is any vertex not on C adjacent to two vertices of C, then u is adjacent to v and b, or to v and c, otherwise we find a hexagon with vertex set V (C) ∪ {u}. If V (G_{t}) ⊂ V (Q_{i}) ∪ V (Q_{j}) for all t ∉ {i, j}, then set S = {i, j}. Suppose G_{t} ⊄ V (Q_{i})∪V (Q_{j}) for some t ∉ {i, j}. As |V (Q_{t})∩V (Q_{i})| ≥ 3 and |V (Q_{t}) ∩ V (Q_{j})| ≥ 3, there is a quadrilateral Q_{t} ⊂ G_{t}, containing e, and a unique vertex u ∈ V (Q_{t})\(V (Q_{i}) ∪ V (Q_{j})). We observed that u is adjacent to v and b or v and c. Suppose u is adjacent to v and b. Then G_{i} and G_{t} consist of a union of paths of length two between v and b. By maximality, this implies G_{i} = G_{t}. So, with S = {i, j}, we are done in the case (3). Suppose (2) holds, and Q_{i} = (v, a, b, c, v) and e = {b, c}. If V (Q_{t}) ⊂ V (Q_{i}) for all t ∉ {i, j}, then we are done with S = {i, j}. So we assume there is t ∉ {i, j} such that V (Q_{t}) ⊄ V (Q_{i}). Since |V (Q_{i}) ∩ V (Q_{t})| ≥ 3, there is a unique vertex u ∈ V (Q_{t})\V (Q_{i}) with two neighbors in Q_{i}. Then at least one of the graphs Q_{i} ∪ Q_{t} or Q_{j} ∪ Q_{t} satisfies (3).

The number of triangles in a graph G is denoted T (G).

Lemma 3.2 Let G = (V, E) be an n-vertex hexagon-free graph with at least n edges, of maximum degree Δ. Then T (G) ≤ 3e(G), and the number of subgraphs of G isomorphic to a graph consisting of two edge-disjoint triangles intersecting in one vertex is at most \frac{9}{4}Δe(G).

Proof. For any vertex v of G, denote by G_{v} the graph spanned by all edges in the neighborhood of a vertex v ∈ G. Since G is hexagon-free, G_{v} contains no path of length four. Therefore, by the Erdős-Gallai Theorem [6], e(G_{v}) ≤ \frac{3}{2}d(v) and

T (G) ≤ ∑_{v∈V} e(G_{v}) ≤ \frac{3}{2} ∑_{v∈V} d(v) = 3e(G),

as required. For the second part, the number of ways of selecting a pair of triangles incident with a single vertex equals the number of way of choosing a vertex v ∈ V, and then choosing two edges of G_{v}, which can be bounded as follows:

∑_{v∈V} \binom{e(G_{v})}{2} ≤ ∑_{v∈V} \binom{3d(v)/2}{2} < \frac{9}{8} ∑_{v∈V} d(v)^{2}.

As G has maximum degree Δ, the vector (d(v))_{v∈G} can only take values in the polytope

K = [1, Δ]^{V} ∩ (2e(G) · Σ_{V} ),

where Σ_{V} is the standard simplex in ℝ^{V}. Since the convex function (x_{v})_{v∈V} ↦ ∑_{v∈V} x_{v}^{2} attains its maximum on K at a vertex of K, it is straightforward to verify that:

∑_{v∈V} d(v)^{2} < Δ^{2} ⌊\frac{2e(G)}{Δ}⌋ + (2e(G) − Δ ⌊\frac{2e(G)}{Δ}⌋)^{2} ≤ \frac{2e(G)}{Δ} · Δ^{2} = 2Δe(G).

Let G be a graph with vertex set V. For every {u, v} ⊂ V, we write P_{{u,v}} for the set of paths of length three between u and v in G, and G_{{u,v}} for the subgraph of G consisting of the union of all paths in P_{{u,v}}. For a vertex v ∈ G, G − v denotes the graph on V \{v} consisting of all edges disjoint from v.

Lemma 3.3 Let G be an n-vertex hexagon-free graph of maximum degree Δ, and let X = {x : |P_{x}| ≥ 3}. Then

∑_{x∈X} |P_{x}| < 36Δe(G).

Proof. Fix a pair {u, v} = x ∈ X. As G contains no hexagon, the edges of G_{x} disjoint from u and v form an intersecting family. It follows that G_{x} − u − v is a triangle or a star. If G_{x} contains a maximal K_{2,t} for some t ≥ |P_{x}|, then denote such a maximal K_{2,t} by K_{x}^{∗}. Otherwise, as |P_{x}| ≥ 3, by definition of X, G_{x} contains a pair of triangles intersecting in one vertex and |P_{x}| = 3; let Y be the set of such pairs x ∈ X. If H denotes a graph comprising of two triangles intersecting in one vertex, then it is straightforward to check that for every subgraph L ⊂ G isomorphic to H,

|{y ∈ Y : G_{y} ⊂ L}| ≤ 2.

Therefore, by Lemma 3.2,

∑_{y∈Y} |P_{y}| = ∑_{\begin{matrix}L⊂G \\ L≅H \end{matrix}} ∑_{\begin{matrix}y∈Y \\ L⊂G_{y} \end{matrix}} 3

= ∑_{\begin{matrix}L⊂G \\ L≅H \end{matrix}} 3 |\{y ∈ Y : G_{y} ⊂ L\}| ≤ ∑_{\begin{matrix}L⊂G \\ L≅H \end{matrix}} 6 ≤ \frac{27}{4}Δe(G) < 14Δe(G).

Consider x ∈ X\Y. By the definition of G_{x} and Y, K_{x}^{∗} is also a maximal complete bipartite subgraph of G. The number of pairs z ∈ X for which K_{z}^{∗} = K_{x}^{∗} is at most 2Δ, since G has maximum degree at most Δ. By Lemma 3.1,

∑_{x∈X\Y} |P_{x}| ≤ ∑_{K∈B(G)} 2Δ · e(K) ≤ 22Δe(G).

Adding the two inequalities above, the proof is complete.

Lemma 3.4 Let G be an n-vertex hexagon-free graph of maximum degree Δ, and let Z = {z : |P_{z}| = 2}. Then

∑_{z∈Z} |P_{z}| ≤ 85Δe(G).

Proof. As in the proof of Lemma 3.3, either G_{z} contains two triangles intersecting in one vertex, or G_{z} contains a quadrilateral C_{z}. Denote by Z′ the set of all pairs z ∈ Z for which C_{z} exists. By Lemma 3.2, the pairs in Z \ Z′ account for 5Δe(G) in the sum above. Let W = {z ∈ Z′ : C_{z} ∈ B(G)}. As the maximum degree of G is Δ, given a quadrilateral C ⊂ G, the number of pairs w ∈ W for which C_{w} = C is at most 4Δ. By Lemma 3.1,

∑_{w∈W} |P_{w}| ≤ 4Δ ∑_{w∈W} e(C_{w}) ≤ 44Δe(G).

For z ∈ Z\W, i.e. when C_{z} ∉ B(G), there exists a pair x ∈ X such that C_{z} ⊂ K_{x}^{∗}, where X is defined in Lemma 3.3. By Lemma 3.3, it follows that

∑_{z∈Z′\W} |P_{z}| ≤ 36Δe(G).

4 The Turán Number for the Hexagon

We now prove Theorem 1.1. Let G = (V, E) be an n-vertex hexagon-free graph. We may assume that G has size at least \frac{1}{2}n^{4/3}, or we are done. By applying the regularization lemma with Δ = n^{4/9}, we may pass to a subgraph of G of maximum degree at most Δ and size at least e(G) − O(n^{10/9}). In what follows, we therefore suppose that G has maximum degree at most Δ. The number of paths of length three in G is precisely

∑_{{u,v}∈E}[d(u) − 1][d(v) − 1] − 3T (G) = ∑_{{u,v}∈E} d(u)d(v) − 2 ∑_{v∈V} d(v)^{2} + e(G) − 3T (G).

By the Blakley-Roy Inequality [3], for any symmetric matrix S with non-negative entries and any vector x with non-negative entries,

⟨S^{3}x, x⟩ ≥ \frac{⟨Sx, x⟩^{3}}{∥x∥^{2}} .

Letting S be the adjacency matrix of G, and x = (1, 1, 1 …, 1) ∈ ℝ^{n}, we find that

∑_{\{u,v\}∈E} d(u)d(v) = \frac{1}{2}⟨S^{3}x, x⟩ ≥ \frac{4e(G)^{3}}{n^{2}} .

As G has maximum degree Δ, it is straightforward to verify (as in Lemma 3.2) that:

2 ∑_{v∈G} d(v)^{2} ≤ 4Δe(G).

By Lemma 3.2, 3T (G) − e(G) ≤ 8e(G) = O(Δe(G)). We therefore conclude that

∑_{x⊂V} |P_{x}| > \frac{4e(G)^{3}}{n^{2}} − O(Δe(G)).

By Lemma 3.3 and Lemma 3.4, the number of paths of length three in G is

∑_{x⊂V} |P_{x}| = ∑_{\begin{matrix}x⊂V \\ |P_{x}|=1 \end{matrix}} |P_{x}| + ∑_{\begin{matrix}x⊂V \\ |P_{x}|≥2 \end{matrix}} |P_{x}| ≤ \binom{n}{2} + O(Δe(G)).

Comparing the inequalities above, we have

\frac{4e(G)^{3}}{n^{2}} ≤ \binom{n}{2} + O(Δe(G)).

Solving for e(G), we find

e(G) ≤ \frac{1}{2}n^{4/3} + O(n^{10/9}).

This concludes the proof of Theorem 1.1.

References

[1] Baker, R. C., Harman, G., Pintz, J. The difference between consecutive primes. II. Proc. London Math. Soc. 83 (2001), no. 3, 532-562.

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

[3] Blakley, G., Roy, P. A Hölder type inequality for symmetric matrices with nonnegative entries. Proc. Amer. Math. Soc. 16 1965 1244–1245.

[4] Bollobás, B. Extremal Graph Theory. In Handbook of Combinatorics (edited by R.L. Graham, M. Grötschel, L. Lovász), 1231-1292, North-Holland, Amsterdam, 1995.

[5] Brown, W.G. On graphs that do not contain a Thomsen graph, Canad. Math. Bull. 9, 281-285 (1966).

[6] Erdős, P., Gallai, T. On maximal paths and circuits of graphs. Acta Math. Acad. Sci. Hungar 10 (1959) 337–356.

[7] Erdős, P., Rényi, A., Sós, V. T. On a problem of graph theory. Studia Sci. Math. Hungar. 1 1966 215–235.

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

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

[10] Füredi, Z. Quadrilateral-free graphs with a maximum number of edges. Preprint.

[11] Füredi, Z. Graphs without quadrilaterals. J Combin. Theory B, 34, 187-190 (1983).

[12] Füredi, Z. Unpublished manuscript.

[13] Kövari, T., Sós, V., Turán, P. On a problem of K. Zarankiewicz. Colloquium Math. 3, (1954). 50–57.

[14] Lazebnik, F., Ustimenko, V. A., Woldar, A. J., A new series of dense graphs of large girth. Bull. Amer. Math. Soc. 32(1), 73-79 (1995).

[15] Lazebnik, F., Ustimenko, V. A., Woldar, A. J., Polarities and 2k-cycle-free graphs. Discrete Math. 197/198 (1999), 503–513.

[16] Naor, A., Verstraëte, J. A. Forbidden Circuit Theorems. Preprint (2003).

[17] Reiman, I. Über ein problem von Zarankiewicz, Acta Acad. Sci. Hungar. 9 (1958), 269-279.

[18] Sárkőzy, G. Cycles in bipartite graphs and an application in number theory. J. Graph Theory 19 (1995), no. 3, 323–331.

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

[20] Turán, P. On an extremal problem in graph theory. (in Hungarian), Mat. Fiz. Lapok 48, 436-452, 1941.

[21] Verstraëte, J. A. Arithmetic progressions of cycle lengths in graphs. Combin. Probab. Comput 9 (2000) no 4. 369–373.

[22] Wenger, R., Extremal graphs with no C^{4}’s, C^{6}’s, or C^{10}’s. J. Combin. Theory Ser. B 52 (1991), no. 1, 113–116.