= Logarithmic clique blow-up from minimum degree
{title2=$\delta(G)\ge(1-1/r+\varepsilon)n\Longrightarrow K_{r+1}(\lfloor d\log n\rfloor)\subseteq G$}
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\varepsilon 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.
Back to article page
