A note on the Turán function of even cycles
HTML articles powered by AMS MathViewer
- by Oleg Pikhurko
- Proc. Amer. Math. Soc. 140 (2012), 3687-3692
- DOI: https://doi.org/10.1090/S0002-9939-2012-11274-2
- Published electronically: March 1, 2012
- PDF | Request permission
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 \[ \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
- Clark T. Benson, Minimal regular graphs of girths eight and twelve, Canadian J. Math. 18 (1966), 1091–1094. MR 197342, DOI 10.4153/CJM-1966-109-8
- J. A. Bondy and U. S. R. Murty, Graph theory, Graduate Texts in Mathematics, vol. 244, Springer, New York, 2008. MR 2368647, DOI 10.1007/978-1-84628-970-5
- J. A. Bondy and M. Simonovits, Cycles of even length in graphs, J. Combinatorial Theory Ser. B 16 (1974), 97–105. MR 340095, DOI 10.1016/0095-8956(74)90052-5
- W. G. Brown, On graphs that do not contain a Thomsen graph, Canad. Math. Bull. 9 (1966), 281–285. MR 200182, DOI 10.4153/CMB-1966-036-2
- C. R. J. Clapham, A. Flockhart, and J. Sheehan, Graphs without four-cycles, J. Graph Theory 13 (1989), no. 1, 29–47. MR 982865, DOI 10.1002/jgt.3190130107
- 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.
- P. Erdős, Extremal problems in graph theory, Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963) Publ. House Czech. Acad. Sci., Prague, 1964, pp. 29–36. MR 0180500
- P. Erdős and A. Rényi, On a problem in the theory of graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 7 (1962), 623–641 (1963) (Hungarian, with English and Russian summaries). MR 193024
- P. Erdős, A. Rényi, and V. T. Sós, On a problem of graph theory, Studia Sci. Math. Hungar. 1 (1966), 215–235. MR 223262
- P. Erdős and M. Simonovits, Compactness results in extremal graph theory, Combinatorica 2 (1982), no. 3, 275–288. MR 698653, DOI 10.1007/BF02579234
- Z. Füredi, Graphs without quadrilaterals, J. Combin. Theory Ser. B 34 (1983), no. 2, 187–190. MR 703603, DOI 10.1016/0095-8956(83)90018-7
- Zoltán Füredi, On the number of edges of quadrilateral-free graphs, J. Combin. Theory Ser. B 68 (1996), no. 1, 1–6. MR 1405701, DOI 10.1006/jctb.1996.0052
- Zoltan Füredi, Assaf Naor, and Jacques Verstraëte, On the Turán number for the hexagon, Adv. Math. 203 (2006), no. 2, 476–496. MR 2227729, DOI 10.1016/j.aim.2005.04.011
- Felix Lazebnik and Vasiliy A. Ustimenko, Explicit construction of graphs with an arbitrary large girth and of large size, Discrete Appl. Math. 60 (1995), no. 1-3, 275–284. ARIDAM VI and VII (New Brunswick, NJ, 1991/1992). MR 1339092, DOI 10.1016/0166-218X(94)00058-L
- F. Lazebnik, V. A. Ustimenko, and A. J. Woldar, Properties of certain families of $2k$-cycle-free graphs, J. Combin. Theory Ser. B 60 (1994), no. 2, 293–298. MR 1271276, DOI 10.1006/jctb.1994.1020
- Felix Lazebnik, Vasiliy A. Ustimenko, and Andrew J. Woldar, Polarities and $2k$-cycle-free graphs, Discrete Math. 197/198 (1999), 503–513. 16th British Combinatorial Conference (London, 1997). MR 1674884
- W. McCuaig, 1985, unpublished letter, see [12, page 1].
- Keith E. Mellinger, LDPC codes from triangle-free line sets, Des. Codes Cryptogr. 32 (2004), no. 1-3, 341–350. MR 2072337, DOI 10.1023/B:DESI.0000029233.20866.41
- Keith E. Mellinger and Dhruv Mubayi, Constructions of bipartite graphs from finite geometries, J. Graph Theory 49 (2005), no. 1, 1–10. MR 2130466, DOI 10.1002/jgt.20059
- P. Turán, On an extremal problem in graph theory (in Hungarian), Mat. Fiz. Lapok 48 (1941), 436–452.
- Jacques Verstraëte, On arithmetic progressions of cycle lengths in graphs, Combin. Probab. Comput. 9 (2000), no. 4, 369–373. MR 1786926, DOI 10.1017/S0963548300004478
- R. Wenger, Extremal graphs with no $C^4$’s, $C^6$’s, or $C^{10}$’s, J. Combin. Theory Ser. B 52 (1991), no. 1, 113–116. MR 1109426, DOI 10.1016/0095-8956(91)90097-4
- Yang Yuansheng and Peter Rowlinson, On extremal graphs without four-cycles, Utilitas Math. 41 (1992), 204–210. MR 1162526
Bibliographic Information
- Oleg Pikhurko
- Affiliation: Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Pennsylvannia 15213
- 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
- © Copyright 2012
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Proc. Amer. Math. Soc. 140 (2012), 3687-3692
- MSC (2010): Primary 05C35
- DOI: https://doi.org/10.1090/S0002-9939-2012-11274-2
- MathSciNet review: 2944709