Raphael Yuster

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

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$. Thei...