= Clique supersaturation by sampling
{title2=$e(G)\ge(1-1/r+\epsilon)\binom n2\Longrightarrow k_{r+1}(G)\ge\eta n^{r+1}$}
Choose a fixed sample size $m$ for which the normalized <Turan theorem> bound lies below the given density by a positive margin. The expected <edge> count in a random $m$-vertex subset then forces a positive proportion of subsets to contain a forbidden-size <clique>. Each <clique> belongs to a known number of subsets, so double counting gives a positive constant times $n^{r+1}$ <cliques>.
Back to article page
