Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-23T14:26:37.378Z Has data issue: false hasContentIssue false
  • English
  • Français

Turán numbers of theta graphs

Part of: Graph theory Extremal combinatorics

Published online by Cambridge University Press:  13 February 2020

Boris Bukh  and
Michael Tait
Boris Bukh*
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA, 15213, USA
Michael Tait
Affiliation:
Department of Mathematics and Statistics, Villanova University, Villanova, PA, 19085, USA
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The theta graph ${\Theta _{\ell ,t}}$ consists of two vertices joined by t vertex-disjoint paths, each of length $\ell $ . For fixed odd $\ell $ and large t, we show that the largest graph not containing ${\Theta _{\ell ,t}}$ has at most ${c_\ell }{t^{1 - 1/\ell }}{n^{1 + 1/\ell }}$ edges and that this is tight apart from the value of ${c_\ell }$ .

MSC classification

Primary: 05C35: Extremal problems
Secondary: 05D99: None of the above, but in this section 05D40: Probabilistic methods
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 29 , Issue 4 , July 2020 , pp. 495 - 507
Check for updates
Copyright
© Cambridge University Press 2020

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

Supported in part by a Sloan Research Fellowship and by US taxpayers through NSF CAREER grant DMS-1555149.

‡

This work was completed while the second author was a postdoc at Carnegie Mellon University and was supported in part by NSF grant DMS-1606350.

References

Baker, R. C., Harman, G. and Pintz, J. (2001) The difference between consecutive primes, II. Proc. London Math. Soc. (3) 83 532–562.CrossRefGoogle Scholar
Benson, C. T. (1966) Minimal regular graphs of girths eight and twelve. Canad. J. Math. 18 1091–1094.Google Scholar
Blagojević, P. V. M., Bukh, B. and Karasev, R. (2013) Turán numbers for K s,t -free graphs: Topological obstructions and algebraic constructions. Israel J. Math. 197 199–214.CrossRefGoogle Scholar
Bondy, J. A. and Simonovits, M. (1974) Cycles of even length in graphs. J. Combin. Theory Ser. B 16 97–105.CrossRefGoogle Scholar
Brown, W. G. (1966) On graphs that do not contain a Thomsen graph. Canad. Math. Bull. 9 281–285.CrossRefGoogle Scholar
Bukh, B. (2015) Random algebraic construction of extremal graphs. Bull. London Math. Soc. 47 939–945.Google Scholar
Bukh, B. and Conlon, D. (2018) Rational exponents in extremal graph theory. J. European Math. Soc. 20 1745–1757.Google Scholar
Bukh, B. and Jiang, Z. (2017) A bound on the number of edges in graphs without an even cycle. Combin. Probab. Comput. 26 1–15. arXiv:1403.1601CrossRefGoogle Scholar
Conlon, D. Graphs with few paths of prescribed length between any two vertices. To appear in Bull. Lond. Math. Soc. arXiv:1411.0856Google Scholar
Erdős, P. (1938) On sequences of integers no one of which divides the product of two others and on some related problems. Isvestia Nauchno-Issl. Inst. Mat. i Meh. Tomsk 2 74–82.Google Scholar
Erdős, P. (1964) Extremal problems in graph theory. In Theory of Graphs and its Applications, Publishing House of the Czechoslovak Academy of Sciences, pp. 29–36.Google Scholar
Erdős, P., Rényi, A. and Sós, V. T. (1966) On a problem of graph theory. Studia Sci. Math. Hungar. 1 215–235.Google Scholar
Erdős, P. and Stone, A. H. (1946) On the structure of linear graphs. Bull. Amer. Math. Soc. 52 1087–1091.Google Scholar
Faudree, R. J. and Simonovits, M. (1983) On a class of degenerate extremal graph problems. Combinatorica 3 83–93.CrossRefGoogle Scholar
Firke, F. A., Kosek, P. M., Nash, E. D. and Williford, J. (2013) Extremal graphs without 4-cycles. J. Combin. Theory Ser. B 103 327–336.CrossRefGoogle Scholar
Füredi, Z. (1983) Graphs without quadrilaterals. J. Combin. Theory Ser. B 34 187–190.CrossRefGoogle Scholar
Füredi, Z. (1994) Quadrilateral-free graphs with the maximum number of edges. In Proceedings of the Japan Workshop on Graph Theory and Combinatorics, Keio University, Yokohama, Japan, pp. 13–22.Google Scholar
Füredi, Z. (1996) New asymptotics for bipartite Turán numbers. J. Combin. Theory Ser. A 75 141–144.CrossRefGoogle Scholar
Füredi, Z. (1996) On the number of edges of quadrilateral-free graphs. J. Combin. Theory Ser. B 68 1–6.CrossRefGoogle Scholar
Füredi, Z., Naor, A. and Verstraëte, J. (2006) On the Turán number for the hexagon. Adv. Math. 203 476–496. https://web.math.princeton.edu/~naor/home pagefiles/final-hexagons.pdf CrossRefGoogle Scholar
Füredi, Z. and Simonovits, M. (2013) The history of degenerate (bipartite) extremal graph problems. In Erdős Centennial, Springer, pp. 169–264.CrossRefGoogle Scholar
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. http://people.maths.ox.ac.uk/keevash/papers/turan-survey.pdf CrossRefGoogle Scholar
Kővari, T., Sós, V. T. and Turán, P. (1954) On a problem of K. Zarankiewicz. Coll. Math. 3 50–57.Google Scholar
Lazebnik, F., Ustimenko, V. A. and Woldar, A. J. (1995) A new series of dense graphs of high girth. Bull. Amer. Math. Soc. (N.S.) 32 73–79.CrossRefGoogle Scholar
Pikhurko, O. (2012) A note on the Turán function of even cycles. Proc. Amer. Math. Soc. 140 3687–3692. https://homepages.warwick.ac.uk/~maskat/Papers/EvenCycle.pdf CrossRefGoogle Scholar
Sidorenko, A. (1995) What we know and what we do not know about Turán numbers. Graphs Combin. 11 179–199.CrossRefGoogle Scholar
Terlep, T. A. and Williford, J. (2012) Graphs from generalized Kac–Moody algebras. SIAM J. Discrete Math. 26 1112–1120.CrossRefGoogle Scholar
Verstraëte, J. (2000) On arithmetic progressions of cycle lengths in graphs. Combin. Probab. Comput. 9 369–373.Google Scholar
Verstraëte, J. and Williford, J. (2019) Graphs without theta subgraphs. J. Combin. Theory Ser. B 134 76–87. http://www.math.ucsd.edu/~jverstra/theta-final.pdf CrossRefGoogle Scholar
Wenger, R. (1991) Extremal graphs with no C4’s, C6’s, or C10’s. J. Combin. Theory Ser. B 52 113–116.CrossRefGoogle Scholar
Xu, Z., Zhang, T. and Ge, G. (2019) Some tight lower bounds for Turán problems via constructions of multi-hypergraphs. arXiv:1907.11909Google Scholar