Turán number for even cycles
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
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\),
For the general case, Erdös [5] and Bondy and Simonovits [6] showed that
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/(2k1)}\) 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 /(3k3)}\). The same authors [8] prove (by construction) that \( t(n, C_{2k})\geq (\frac{k1}{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),
5057.

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

3 
Z. Füredi,
On the number of edges of quadrilateralfree graphs,
J. Comb. Theory Ser. B 68 (1996), 16.

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), 2936.

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

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

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), 293298.

9  F. Lazebnik, V. A. Ustimenko, A. J. Woldar. Polarities and \( 2k\)cyclefree graphs. Disc. Math. 197/198 (1999), 503513.

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), 261277.

13  G. A. Margulis. Arithmetic groups and graphs without short cycles. 6th Internat. Symp. on Information Theory, Tashkent (1984) Abstracts 1, 123125 (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), 7379.
