Turán number for even cycles

For a graph \( G\), define the Turán number \( t(n, G)\) to be the largest integer \( m\) such that there exists a graph on \( n\) vertices with \( m\) edges that does not contain \( G\) as a subgraph. In other words, if \( H\) has \( n\) vertices and more than \( t(n, G)\) edges, then \( H\) must contain \( G\) as a subgraph.

It is easy to see that for odd cycles, the Turán number \( t(n,C_{2k+1})= \lfloor n^2/4 \rfloor\) for \( n > 2k+1\), since no bipartite graph contains an odd cycle. However, the problem of determining the Turán numbers for even cycles is still open.

For the \( 4\)-cycle \( C_4\), it was known [1] for some time that the Turán number \( t(n, C_4)\) is of order \( n^{3/2}\). In 1983, Füredi [2] determined the exact values of \( t(n, C_4)\) for infinitely many \( n\) (in particular, for \( n=2^k\) for some \( k\)). In 1996, Füredi generalized this result [3]. He proved that for \( q \geq 15\) and \( n=q^2+q+1\),

\(\displaystyle t(n,C_4) \leq \frac{1}{2} q(q+1)^2. \)

In particular, for a prime power \( p \geq 13\) and \( n=p^2+p+1\),

\(\displaystyle t(n,C_4) = \frac{1}{2} p(p+1)^2. \)

Exact values of \( t(n, C_4)\) are known for all \( n\leq 21\) (see, for example, [4]).

For the general case, Erdös [5] and Bondy and Simonovits [6] showed that

\(\displaystyle t(n,C_{2k}) \leq c k n^{1+1/k}. \)

Erdös also posed the following conjecture:

Conjecture (Proposed by Erdös[5])

Prove that \[ t(n,C_{2k}) \geq cn^{1+1/k} \] for \(k =4\) and \(k \geq 6\).

We note that this conjecture, together with the above result of Erdös, Bondy and Simonovits, would imply that \( t(n, C_{2k})=o_n(n^{1+1/k})\). In fact, it has been conjectured by Erdös and Simonovits[7] that \( t(n, C_{2k})=(\frac{1}{2}+o(1))n^{1+1/k})\). For the case that \( k=5\), Lazebnik, Ustimenko, and Woldar [8] disprove this second conjecture, showing that \( t(n, C_{2k})>(c+o(1))n^{1+1/k})\), where \( c\approx 0.58\) (see also [9] for a further discussion on this counterexample). This was also disproven in the case that \( k=3\) by Füredi, Naor, and Verstraëte [10].

A lower bound of order \( n^{1+1/(2k-1)}\) for the above conjecture can be proved by probabilistic deletion methods [11]. The bipartite Ramanujan graph[12], [13] shows that \( t(n,C_{2k}) \geq n^{1+2/3k}\). In 1995, Lazebnik, Ustimenko and Woldar [14] constructed graphs which yield \( t(n,C_{2k}) \geq n^{1+ 2 /(3k-3)}\). The same authors [8] prove (by construction) that \( t(n, C_{2k})\geq (\frac{k-1}{k^{1+1/k}}+o(1))n^{1+1/k}\) (it is this construction that yields the counterexample to Erdös and Simonovits' conjecture, as noted above).

1 T. Kövári, V. T. Sós and P. Turán, On a problem of K. Zarankiewicz, Colloq. Math. 3 (1954), 50-57.

2 Z. Füredi, Graphs without quadrilaterals, J. Comb. Theory Ser. B 34 (1983), 187-190.

3 Z. Füredi, On the number of edges of quadrilateral-free graphs, J. Comb. Theory Ser. B 68 (1996), 1-6.

4 C. R. J. Claphan, A. Flockhart and J. Sheehan. Graphs without four- cycles. J. Graph Theory 13 (1989), 2947.

5 P. Erdös. Extremal problems in graph theory, Theory of Graphs and its Applications, (M. Fiedler ed.) (Proc. Symp. Smolenice, 1963), Academic Press, New York (1965), 29-36.

6 J. A. Bondy and M. Simonovits. Cycles of even length in graphs. J. Comb. Theory B 16 (1974), 97-105.

7 P. Erdös and M. Simonovits, Compactness results in extremal graph theory, Combinatorica 2 (1982), 275-288.

8 F. Lazebnik, V.A. Ustimenko, A.J. Woldar. Properties of certain families of \( 2k\)-cycle free graphs. J. Combin. Theory Set. B 60(2) (1994), 293-298.

9 F. Lazebnik, V. A. Ustimenko, A. J. Woldar. Polarities and \( 2k\)-cycle-free graphs. Disc. Math. 197/198 (1999), 503-513.

10 Z. Füredi, A. Naor, and J. Verstraëte. On the Turán number for the hexagon. Adv. Math. 203 (2006), 476496.

11 P. Erdös and J. H. Spencer, Probabilistic Methods in Combinatorics, Probability and Mathematical Statistics, Vol. 17, Academic Press, New York, 1974.

12 A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), 261-277.

13 G. A. Margulis. Arithmetic groups and graphs without short cycles. 6th Internat. Symp. on Information Theory, Tashkent (1984) Abstracts 1, 123-125 (in Russian).

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