No CrossRef data available.
Article contents
Turán numbers of theta graphs
Published online by Cambridge University Press: 13 February 2020
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.
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
Information
- Type
- Paper
- Information
- Copyright
- © Cambridge University Press 2020
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
You have
Access
- 18
- Cited by