Turán numbers of theta graphs

Abstract

The theta graph ${\Theta }_{\ell ,t}$ consists of two vertices joined by $t$ vertex-disjoint paths of length $\ell$ each. 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 }$.

Revised to reflect referee comments. To appear in Combinatorics, Probability and Computing

Cited by in corpus (1)

• Some tight lower bounds for Turán problems via constructions of multi-hypergraphs