A Tight Erdős-Stone Bound for All Graph Densities

Abstract

The Erdő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átal--Szemerédi 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ős--Stone problem for all edge densities. More precisely, we prove that for every integer $r\ge 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övari-Sós-Turán-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.