A note on the Turán function of even cycles

Pikhurko, Oleg

doi:10.1090/S0002-9939-2012-11274-2

A note on the Turán function of even cycles
HTML articles powered by AMS MathViewer

by Oleg Pikhurko PDF

Proc. Amer. Math. Soc. 140 (2012), 3687-3692 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