A Tight Erd\H{o}s-Stone Bound for All Graph Densities

Abstract

The Erd\H{o}s--Stone Theorem asserts that if a graph has edge density $1-1/r+\delta$ then it contains a complete $(r+1)$-partite graph with $b$ vertices in each part, where $b=b_n(r,\delta) \gg 1$. The celebrated Chv\'atal--Szemer\'edi theorem determined the exact order of $b_n(r,\delta)$ for every $\delta<1/r^3$. Their bound, however, is not tight when $\delta=1/r-\epsilon$, that is, when the graph has edge density $1-\epsilon$ for small $\epsilon$. Our main result in this paper determines the correct order in this remaining regime, thereby enabling us to give a tight bound for the Erd\H{o}s--Stone problem for all edge densities. More precisely, we prove that for every integer $r\geq 2$ and $0<\delta<1/r$ we have $$ b_n(r,\delta)=\Theta\left(\frac{\log n}{(1/r-\delta)r\log(1/\delta)}\right)\;. $$ The lower bound is obtained using a K\"{o}vari-S\'os-Tur\'an-type argument combined with a variant of Nikiforov's method of constructing large blow-ups, while the upper bound is proved using a correlated random graph construction, related to tensor powers.