= High-minimum-degree multipartite stability subgraph
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>.
Back to article page
