Fixed-size clique appearance threshold (${\mu }_n=\left(\genfrac{}{}{0ex}{}{n}{k}\right)p^{\left(\genfrac{}{}{0ex}{}{k}{2}\right)}$)

For fixed $k\ge 2$, a binomial random graph has no $k$-cliques with probability tending to one if ${\mu }_n\to 0$, 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\ge 2$ contribute $O(n^{-l}{p}^{-\left(\genfrac{}{}{0ex}{}{l}{2}\right)})$, and each contribution tends to zero above this threshold. The fixed-size qualification matters.

With these parameters the expected number of $(n-1)$-cliques is asymptotic to $\sqrt{n}$, yet the probability of any such clique tends to zero. The complement graph has about $\frac{1}{2}\log n$ edges, and with probability tending to one two of them are vertex disjoint. Deleting one vertex cannot remove both edges. Thus divergence of the expected clique count alone does not give an appearance theorem for arbitrary growing clique size.