Clique count in a binomial random graph

If $X_t$ counts copies of the complete graph $K_t$ in $G(n,p)$, thenConsequently $p{n}^{2/(t-1)}\to 0$ implies $\mathbb{P}(X_t>0)\to 0$ by the first moment method.

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.

For the number $X$ of $k$-cliques in a binomial random graph $G(n,p)$, with $0<p<1$ and $\mu =\mathbb{E}X$,Two $k$-sets overlapping in $j$ vertices share $\left(\genfrac{}{}{0ex}{}{j}{2}\right)$ edges. Overlaps of zero or one vertex give independent indicators; $j=k$ includes the diagonal terms. The identity is useful for the second moment method.

Write ${\mu }_r=\left(\genfrac{}{}{0ex}{}{n}{r}\right)p^{\left(\genfrac{}{}{0ex}{}{r}{2}\right)}$ and $T_s=\left(\genfrac{}{}{0ex}{}{r}{s}\right)\left(\genfrac{}{}{0ex}{}{n-r}{r-s}\right)p^{-\left(\genfrac{}{}{0ex}{}{s}{2}\right)}/\left(\genfrac{}{}{0ex}{}{n}{r}\right)$. The first mean condition implies $p^{-1}\le (en/r{)}^{2/(r-1)}$ eventually. For $2\le s\le r/2$, this yields $T_s\le (C/s{)}^s$, and each fixed-$s$ term tends to zero when $n\ge r^3$. The second mean condition implies $p\le ((r+1)/n{)}^{2/r}$ eventually. Writing $s=r-j$ gives $T_{r-j}={\mu }_r^{-1}\left(\genfrac{}{}{0ex}{}{r}{j}\right)\left(\genfrac{}{}{0ex}{}{n-r}{j}\right)p^{j(2r-j-1)/2}\le {\mu }_r^{-1}(C/j{)}^j$ for $1\le j\le r/2$, and $T_r={\mu }_r^{-1}$. Both bounding series are summable. The overlap formula for the variance of a clique count therefore gives relative variance tending to zero; the second moment method proves an $r$-clique exists with high probability.