= Solution
The <binomial random graph> $G(n,p)$ has vertex set $[n]=\{1,\ldots,n\}$, and each unordered pair of distinct vertices is included as an <edge of a graph>[edge] independently with probability $p$.
Let $X_t$ count copies of the <complete graph> $K_t$. Each $t$-element vertex set forms a copy with probability $p^{\binom t2}$, so <linearity of expectation> gives
$$
\mathbb EX_t=\binom ntp^{\binom t2}.
$$
The event $E_t$ is $\{X_t\geq1\}$. By the <first moment method>,
$$
\begin{aligned}
\mathbb P(E_t)
&\leq\mathbb EX_t\\
&\leq\frac{n^t}{t!}p^{t(t-1)/2}\\
&=\frac1{t!}
\left(pn^{2/(t-1)}\right)^{t(t-1)/2}
\longrightarrow0.
\end{aligned}
$$
This is the <clique count in a binomial random graph>.
Back to article page
