Erdős-Stone theorem

For every graph $H$ with chromatic number $r+1$,

An edge density exceeding the Turan theorem threshold for $K_{r+1}$ by a fixed positive amount forces a balanced $K_{r+1}(t)$ subgraph with logarithmic part size. Combine clique supersaturation by sampling with the dense clique family blow-up lemma. Dense binomial random graphs show that the logarithmic order is optimal for a uniform density guarantee.

A fixed positive excess over the Turan theorem threshold forces logarithmic balanced complete multipartite graphs. There is an elementary induction using common neighbourhood from bipartite density: first obtain a logarithmic $r$-partite subgraph from the induction hypothesis, and select disjoint transversal $r$-cliques in it. Each such clique has at least $r\epsilon n$ common neighbours, by the union bound on non-neighbour sets. Apply the bipartite common-neighbour count to these cliques as left-side objects. Their selected union and a large common neighbourhood form the extra part.

In a binomial random graph with fixed edge probability below one, the displayed first-moment bound tends to zero for $t=C\log n$ and sufficiently large fixed $C$. At the same time the edge density concentrates near $p$. Thus a positive fixed density cannot force balanced complete multipartite subgraphs whose part size grows faster than logarithmically.

For fixed positive integers $r,t$, a graph $G$ on $n$ vertices with $e(G)=(1-1/r+o(1))n^2/2$ and no balanced complete multipartite blow-up $K_{r+1}(t)$ contains an $r$-partite subgraph $H$ with $n-o(n)$ vertices, balanced classes of size $n/r+o(n)$, and minimum degree of a graph $\delta (H)=(1-1/r+o(1))n$.

One proof first removes a vanishing fraction of vertices of low degree of a vertex, finds a slowly growing $K_r(L)$ by the Erdős-Stone theorem, and assigns almost every remaining vertex to a root class in which it has fewer than $t$ neighbours of a vertex. After discarding a further vanishing fraction, a $K_{t,t}$ inside an assigned class would extend to $K_{r+1}(t)$ using the root classes. Thus internal edges and missing cross-class edges both number $o(n^2)$. Removing the vertices with unusually many missing cross-class edges gives the stated minimum degree of a graph.

If a fixed graph $F$ has chromatic number $r+1$, every extremal $F$-free graph $G$ on $n$ vertices has minimum degree of a graph $(1-1/r+o(1))n$. Use a high-minimum-degree multipartite stability subgraph $H$: replacing any vertex by one adjacent to all but one class of $H$ preserves $F$-freeness. Any supposed new copy of $F$ can replace the new vertex by an unused common neighbour in the omitted class. Extremality therefore gives the lower bound on every degree of a vertex; the Erdős-Stone theorem gives the upper bound on the average degree of a vertex.