= Solution
Count each unordered $k$-vertex set once. For each such set $A$, let $I_A$ be its <clique> indicator in the <binomial random graph>. All $\binom k2$ required edges are independent, so
$$
X=\sum_{|A|=k}I_A,\qquad
\mu_n=\mathbb EX=\binom nkp^{\binom k2}.
$$
The <Markov inequality>, or <first moment method>, gives
$$
\mathbb P(X\ge1)\le\mathbb EX=\mu_n.
$$
Consequently
$$
\boxed{\mu_n\to0\quad\Longrightarrow\quad\mathbb P(X=0)\to1.}
$$
This argument works even if $k=k(n)$ varies. The <binomial coefficient> shows that <cliques> are counted as vertex sets, not as their different ordered listings.
Back to article page
