The Turán number of sparse spanning graphs

Abstract

For a graph $H$, the {\em extremal number} $ex(n,H)$ is the maximum number of edges in a graph of order $n$ not containing a subgraph isomorphic to $H$. Let $\delta (H)>0$ and $\Delta (H)$ denote the minimum degree and maximum degree of $H$, respectively. We prove that for all $n$ sufficiently large, if $H$ is any graph of order $n$ with $\Delta (H)\le \sqrt{n}/200$, then $ex(n,H)=\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)+\delta (H)-1$. The condition on the maximum degree is tight up to a constant factor. This generalizes a classical result of Ore for the case $H=C_n$, and resolves, in a strong form, a conjecture of Glebov, Person, and Weps for the case of graphs. A counter-example to their more general conjecture concerning the extremal number of bounded degree spanning hypergraphs is also given.