Erdős–Stone theorem

Remarks

The main consequence is a formula for the extremal number. Let $H$ be a graph with chromatic number $\chi(H) = r + 1 \ge 2$. Then $H$ is a subgraph of $K_{r+1}(t)$ for $t = |V(H)|$, and the Turán graph $T(n, r)$ is $H$-free, so $$\mathrm{ex}(n, H) = \left(1 - \frac{1}{r}\right) \frac{n^2}{2} + o(n^2) \quad (n \to \infty).$$ For example, the Petersen graph has chromatic number $3$, so a graph on $n$ vertices with no Petersen subgraph has at most $n^2/4 + o(n^2)$ edges. For bipartite $H$ ($r = 1$) the formula only says $\mathrm{ex}(n, H) = o(n^2)$; the true order is the subject of the Zarankiewicz problem. A modern proof applies the Szemerédi regularity lemma to find a dense $K_{r+1}$ in the reduced graph, and then a counting lemma to blow it up to $K_{r+1}(t)$.

Going deeper

For a student

The theorem is often called the fundamental theorem of extremal graph theory. It gives $\mathrm{ex}(n, H) / \binom{n}{2} \to 1 - \frac{1}{\chi(H) - 1}$ for every graph $H$ with at least one edge. It is sharp for non-bipartite $H$ and degenerate for bipartite $H$, where the extremal number is $o(n^2)$. Stability results refine it: an $H$-free graph with nearly $\mathrm{ex}(n, H)$ edges is close in structure to the Turán graph.