Hostname: page-component-745bb68f8f-s22k5 Total loading time: 0 Render date: 2025-02-06T18:54:41.004Z Has data issue: false hasContentIssue false
  • English
  • Français

A Bound on the Number of Edges in Graphs Without an Even Cycle

Part of: Graph theory Extremal combinatorics

Published online by Cambridge University Press:  07 April 2016

BORIS BUKH  and
ZILIN JIANG
BORIS BUKH
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA (e-mail: bbukh@math.cmu.edu)
ZILIN JIANG
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA (e-mail: zj@cmu.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We show that, for each fixed k, an n-vertex graph not containing a cycle of length 2k has at most $80\sqrt{k\log k}\cdot n^{1+1/k}+O(n)$ edges.

MSC classification

Primary: 05C35: Extremal problems
Secondary: 05D99: None of the above, but in this section 05C38: Paths and cycles
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 1 , January 2017 , pp. 1 - 15
Copyright
Copyright © Cambridge University Press 2016 

References

[1] Benson, C. T. (1966) Minimal regular graphs of girths eight and twelve. Canad. J. Math. 18 1091–1094.Google Scholar
[2] Blagojević, P. V. M., Bukh, B. and Karasev, R. (2013) Turán numbers for Ks,t -free graphs: Topological obstructions and algebraic constructions. Israel J. Math. 197 199–214. arXiv:1108.5254.CrossRefGoogle Scholar
[3] Bondy, J. A. and Simonovits, M. (1974) Cycles of even length in graphs. J. Combin. Theory Ser. B 16 97–105.Google Scholar
[4] Brown, W. G. (1966) On graphs that do not contain a Thomsen graph. Canad. Math. Bull. 9 281–285.Google Scholar
[5] Erdős, P. (1938) 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 74–82.Google Scholar
[6] Erdős, P. (1964) Extremal problems in graph theory. In Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), Publ. House Czechoslovak Academy of Sciences, Prague, pp. 29–36.Google Scholar
[7] Erdős, P. and Rényi, A. (1962) On a problem in the theory of graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl. 7 623–641.Google Scholar
[8] Füredi, Z. and Simonovits, M. (2013) The history of degenerate (bipartite) extremal graph problems. Bolyai Soc. Math. Stud. 25 169–264. arXiv:1306.5167.Google Scholar
[9] Füredi, Z., Naor, A. and Verstraëte, J. (2006) On the Turán number for the hexagon. Adv. Math. 203 476–496.Google Scholar
[10] Keevash, P. (2011) Hypergraph Turán problems. In Surveys in Combinatorics 2011, Vol. 392 of London Mathematical Society Lecture Note Series, Cambridge University Press, pp. 83–139.Google Scholar
[11] Kővari, T., Sós, V. T. and Turán, P. (1954) On a problem of K. Zarankiewicz. Colloquium Math. 3 50–57.Google Scholar
[12] Lazebnik, F. and Ustimenko, V. A. (1995) Explicit construction of graphs with an arbitrary large girth and of large size. Discrete Appl. Math. 60 275–284.Google Scholar
[13] Mellinger, K. E. and Mubayi, D. (2005) Constructions of bipartite graphs from finite geometries. J. Graph Theory 49 1–10.Google Scholar
[14] Pikhurko, O. (2012) A note on the Turán function of even cycles. Proc. Amer. Math. Soc. 140 3687–3692.Google Scholar
[15] Sidorenko, A. (1995) What we know and what we do not know about Turán numbers. Graphs Combin. 11 179–199.Google Scholar
[16] Simonovits, M. (1968) A method for solving extremal problems in graph theory, stability problems. In Theory of Graphs: Proc. Colloq. Tihany 1966, Academic, pp. 279–319.Google Scholar
[17] Turán, P. (1941) On an extremal problem in graph theory (in Hungarian). Mat. Fiz. Lapok 48 436–452.Google Scholar
[18] Verstraëte, J. (2000) On arithmetic progressions of cycle lengths in graphs. Combin. Probab. Comput. 9 369–373. arXiv:math/0204222.CrossRefGoogle Scholar
[19] Wenger, R. (1991) Extremal graphs with no C 4's, C 6's, or C 10's. J. Combin. Theory Ser. B 52 113–116.Google Scholar