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  for some time that the Turán number $$t(n, C_4)$$ is of order $$n^{3/2}$$. In 1983, Füredi  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 . 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, ).

For the general case, Erdös  and Bondy and Simonovits  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)

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 that $$t(n, C_{2k})=(\frac{1}{2}+o(1))n^{1+1/k})$$. For the case that $$k=5$$, Lazebnik, Ustimenko, and Woldar  disprove this second conjecture, showing that $$t(n, C_{2k})>(c+o(1))n^{1+1/k})$$, where $$c\approx 0.58$$ (see also  for a further discussion on this counterexample). This was also disproven in the case that $$k=3$$ by Füredi, Naor, and Verstraëte .

A lower bound of order $$n^{1+1/(2k-1)}$$ for the above conjecture can be proved by probabilistic deletion methods . The bipartite Ramanujan graph,  shows that $$t(n,C_{2k}) \geq n^{1+2/3k}$$. In 1995, Lazebnik, Ustimenko and Woldar  constructed graphs which yield $$t(n,C_{2k}) \geq n^{1+ 2 /(3k-3)}$$. The same authors  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).

Bibliography
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), 29Đ47.

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), 476Đ496.

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.