= Solution
For the <clique count in a binomial random graph>, write
$$
\mu_r=\mathbb EX_r=\binom nr2^{-\binom r2},\qquad L=\log_2n.
$$
Fix $0<\varepsilon<1$. At $r_- =\lfloor(2-\varepsilon)L\rfloor$, the estimates $\binom nr\geq(n/r)^r$ and $r=O(L)$ give
$$
\log_2\mu_{r_-}\geq r_-L-\frac{r_-(r_--1)}2-r_-\log_2r_-
=\left(\varepsilon-\frac{\varepsilon^2}{2}\right)L^2-O(L\log L).
$$
This eventually exceeds $(9/5)L$. At $r_+=\lceil(2+\varepsilon)L\rceil$, the upper bound $\binom nr\leq n^r$ instead gives
$$
\log_2\mu_{r_+}\leq-\left(\varepsilon+\frac{\varepsilon^2}{2}\right)L^2+O(L),
$$
so $\mu_{r_+}<n^{9/5}$. Moreover
$$
\frac{\mu_{r+1}}{\mu_r}=\frac{n-r}{r+1}\,2^{-r}<1\qquad(r\geq r_+),
$$
so no later <clique> size can regain the threshold. The maximum defining $r_0$ exists for sufficiently large $n$, since $\mu_2=\binom n2/2\geq n^{9/5}$ then. We have $r_-\leq r_0<r_+$. Letting $\varepsilon$ decrease to zero proves \b[the asymptotic size]:
$$
\boxed{r_0=(2+o(1))\log_2n.}
$$
Back to article page
