Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

A note on the Turán function of even cycles


Author: Oleg Pikhurko
Journal: Proc. Amer. Math. Soc. 140 (2012), 3687-3692
MSC (2010): Primary 05C35
DOI: https://doi.org/10.1090/S0002-9939-2012-11274-2
Published electronically: March 1, 2012
MathSciNet review: 2944709
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The Turán function $ \mathrm {ex}(n,F)$ is the maximum number of edges in an $ F$-free graph on $ n$ vertices. The question of estimating this function for $ F=C_{2k}$, the cycle of length $ 2k$, is one of the central open questions in this area that goes back to the 1930s. We prove that

$\displaystyle \mathrm {ex}(n,C_{2k})\le (k-1)\, n^{1+1/k}+16(k-1)n, $

improving the previously best known general upper bound of Verstraëte [Combin.Probab. Computing 9 (2000), 369-373] by a factor $ 8+o(1)$ when $ n\gg k$.

References [Enhancements On Off] (What's this?)

  • 1. C. T. Benson, Minimal regular graphs of girths eight and twelve, Can.J. Math. 26 (1966), 1091-1094. MR 0197342 (33:5507)
  • 2. J. A. Bondy and U. S. R. Murty, Graph theory, Graduate Texts in Math., vol. 244, Springer-Verlag, New York, 2008. MR 2368647 (2009c:05001)
  • 3. J. A. Bondy and M. Simonovits, Cycles of even length in graphs, J.Combin. Theory (B) 16 (1974), 97-105. MR 0340095 (49:4851)
  • 4. W. G. Brown, On graphs that do not contain a Thomsen graph, Can.Math. Bull. 9 (1966), 281-289. MR 0200182 (34:81)
  • 5. C. R. J. Clapham, A. Flockhart, and J. Sheehan, Graphs without four-cycles, J. Graph Theory 13 (1989), 29-47. MR 982865 (90d:05126)
  • 6. P. Erdős, On sequences of integers no one of which divides the product of two others and on some related problems., Inst. Math. Mech.Univ. Tomsk 2 (1938), 74-82.
  • 7. P. Erdős, Extremal problems in graph theory, Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), Publ. House Czechoslovak Acad. Sci., Prague, 1964, pp. 29-36. MR 0180500 (31:4735)
  • 8. P. Erdős and A. Rényi, On a problem in the theory of graphs, Publ. Math. Inst. Hung. Acad. Sci. 7 (1962), 623-641 (in Hungarian). MR 0193024 (33:1246)
  • 9. P. Erdős, A. Rényi, and V. T. Sós, On a problem of graph theory, Stud. Sci. Math. Hungar. 1 (1966), 215-235. MR 0223262 (36:6310)
  • 10. P. Erdős and M. Simonovits, Compactness results in extremal graph theory, Combinatorica 2 (1982), 275-288. MR 698653 (84g:05083)
  • 11. Z. Füredi, Graphs without quadrilaterals, J. Combin. Theory (A) 34 (1983), 187-190. MR 703603 (85b:05104)
  • 12. Z. Füredi, On the number of edges of quadrilateral-free graphs, J.Combin. Theory (B) 68 (1996), 1-6. MR 1405701 (97g:05101)
  • 13. Z. Füredi, A. Naor, and J. Verstraëte, On the Turán number for the hexagon, Adv. Math. 203 (2006), 476-496. MR 2227729 (2007b:05104)
  • 14. F. Lazebnik and V. A. Ustimenko, Explicit construction of graphs with an arbitrary large girth and of large size, Discrete Applied Math. 60 (1995), 275-284, ARIDAM VI and VII (New Brunswick, NJ, 1991/1992). MR 1339092 (96e:05088)
  • 15. F. Lazebnik, V. A. Ustimenko, and A. J. Woldar, Properties of certain families of $ 2k$-cycle-free graphs, J. Combin. Theory (B) 60 (1994), 293-298. MR 1271276 (95a:05050)
  • 16. F. Lazebnik, V. A. Ustimenko, and A. J. Woldar, Polarities and $ 2k$-cycle-free graphs, Discrete Math. 197/198 (1999), 503-513, 16th British Combinatorial Conference (London, 1997). MR 1674884 (99i:05123)
  • 17. W. McCuaig, 1985, unpublished letter, see [12, page 1].
  • 18. K. E. Mellinger, LDPC codes from triangle-free line sets, Des. Codes Cryptogr. 32 (2004), 341-350. MR 2072337 (2005b:94056)
  • 19. K. E. Mellinger and D. Mubayi, Constructions of bipartite graphs from finite geometries,
    J. Graph Theory 49 (2005), 1-10. MR 2130466 (2005k:05057)
  • 20. P. Turán, On an extremal problem in graph theory (in Hungarian), Mat. Fiz. Lapok 48 (1941), 436-452.
  • 21. J. Verstraëte, On arithmetic progressions of cycle lengths in graphs, Combin. Probab. Computing 9 (2000), 369-373. MR 1786926 (2001i:05097)
  • 22. R. Wenger, Extremal graphs with no $ {C}\sp 4$'s, $ {C}\sp 6$'s, or $ {C}\sp {10}$'s, J. Combin. Theory (B) 52 (1991), 113-116. MR 1109426 (92c:05085)
  • 23. Y. Yuansheng and P. Rowlinson, On extremal graphs without four-cycles, Utilitas Math. 41 (1992), 204-210. MR 1162526 (92m:05107)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05C35

Retrieve articles in all journals with MSC (2010): 05C35


Additional Information

Oleg Pikhurko
Affiliation: Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Pennsylvannia 15213

DOI: https://doi.org/10.1090/S0002-9939-2012-11274-2
Received by editor(s): September 23, 2010
Received by editor(s) in revised form: April 20, 2011
Published electronically: March 1, 2012
Additional Notes: The author was partially supported by the National Science Foundation, Grant DMS-0758057.
Communicated by: Jim Haglund
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society