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/(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).
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.
|