= Fixed-size clique appearance threshold
{title2=$\mu_n=\binom nkp^{\binom k2}$}
For fixed $k\ge2$, a <binomial random graph> has no $k$-<cliques> with probability tending to one if $\mu_n\to0$, and has at least one with probability tending to one if $\mu_n\to\infty$. The first assertion uses the <first moment method>. The second uses the <overlap formula for the variance of a clique count>: overlapping $k$-sets with $l\ge2$ contribute $O(n^{-l}p^{-\binom l2})$, and each contribution tends to zero above this threshold. The fixed-size qualification matters.
Back to article page
