= Solution
Let $X_t$ count $t$-<cliques>, and put $\mu_t=\binom ntp^{\binom t2}$. Since $\mu_{r+1}\to0$, the <Markov inequality> gives $\Pr(X_{r+1}>0)\to0$. Any larger <clique> contains an $(r+1)$-clique, so it remains to prove $X_r>0$ <with high probability>.
We give the required <growing-clique overlap bound> explicitly. Set $\mu=\mu_r$ and, for $2\leq s\leq r$,
$$
a_s=\frac{\binom rs\binom{n-r}{r-s}}{\binom nr},\qquad T_s=a_sp^{-\binom s2}.
$$
The quantity $a_s$ is the <probability> that a uniformly chosen $r$-set overlaps a fixed $r$-set in exactly $s$ <vertices>. Two clique indicators share exactly $\binom s2$ edge requirements, so their joint-to-product ratio is $p^{-\binom s2}$. Overlap zero or one gives independence. Hence the <overlap formula for the variance of a clique count> implies
$$
\frac{\operatorname{Var}X_r}{\mu^2}=\sum_{s=2}^r a_s\bigl(p^{-\binom s2}-1\bigr)\leq\sum_{s=2}^r T_s.
$$
We must bound this sum with $r$ allowed to grow.
Eventually $\mu_r\geq1$ and $\mu_{r+1}\leq1$. Using $(n/t)^t\leq\binom nt\leq(en/t)^t$, these inequalities give
$$
p^{-1}\leq(en/r)^{2/(r-1)},\qquad p\leq((r+1)/n)^{2/r}.
$$
For $2\leq s\leq r/2$, a <union bound> over the $s$ selected shared vertices gives $a_s\leq\binom rs(r/(n-r))^s$. Put $a=(s-1)/(r-1)<1/2$. Since $n\geq r^3$ and $n-r\geq n/2$,
$$
T_s\leq\left[\frac{2er^2}{sn}(en/r)^a\right]^s\leq\left[\frac{2e^2}{s}r^{-1+2a}\right]^s\leq\left(\frac{2e^2}{s}\right)^s.
$$
For each fixed $s$, the first bound tends to zero if $r$ stays bounded, because its power of $n$ is negative. If $r\to\infty$, the middle bound tends to zero because $a\to0$. Thus each fixed-$s$ term tends to zero along arbitrary admissible sequences. The bounding <series> $\sum_{s\geq2}(2e^2/s)^s$ converges. Splitting at a fixed large index, then taking $n\to\infty$ and the index to infinity, proves that the entire lower-half sum is $o(1)$.
For the upper half write $s=r-j$. The exact diagonal comparison is
$$
T_{r-j}=\frac1\mu\binom rj\binom{n-r}j p^{j(2r-j-1)/2},\qquad T_r=\frac1\mu.
$$
For $1\leq j\leq r/2$, the second bound on $p$ gives
$$
\mu T_{r-j}\leq\left[\frac{e^2r(r+1)^2}{nj^2}\left(\frac n{r+1}\right)^{(j+1)/r}\right]^j\leq\left[\frac{2e^2r^{2(j+1)/r}}{j^2}\right]^j.
$$
The last inequality uses $n\geq r^3$: the exponent of $n$ in the bracket is negative, so substituting $n=r^3$ bounds it above. Uniformly for this range of $j$, $r^{2(j+1)/r}\leq9j$. Indeed $r^{2/r}\leq3$, and concavity of $\log(3j)-(2j/r)\log r$, checked at $j=1$ and $j=r/2$, gives $r^{2j/r}\leq3j$. It follows that
$$
\sum_{s>r/2}T_s\leq\frac1\mu\left[1+\sum_{j\geq1}\left(\frac{18e^2}{j}\right)^j\right]=O(\mu^{-1})=o(1).
$$
Thus $\operatorname{Var}X_r=o(\mu^2)$. The <second moment method> gives $\Pr(X_r=0)\to0$. Combining this with the absence of larger <cliques> proves
$$
\boxed{\Pr\bigl(\text{clique number of }G_{n,p}=r\bigr)\longrightarrow1.}
$$
The restriction on $r$ is used in both overlap ranges; divergence of a <clique count in a binomial random graph> alone would not suffice for arbitrary growing $r$.
Back to article page
