= Solution
Write $p=p(n)$ and let $T$ be the <triangle count in a binomial random graph>. For every three-element <set> $S$ of <vertices>, let $I_S$ be the <indicator random variable> that its three <edges> are present. Then
$$
T=\sum_{|S|=3}I_S,\qquad \mu=\mathbb ET=\binom n3p^3.
$$
For two distinct triples $S,R$, their <indicator random variables> are <independent random variables> unless they share an <edge>. Sharing just one <vertex> still leaves the sets of relevant <edges> disjoint. If they share an <edge>, their union has five <edges>, and therefore
$$
\operatorname{Cov}(I_S,I_R)=p^5-p^6.
$$
There are $\binom n2\binom{n-2}2$ unordered pairs of distinct <triangles in a graph> sharing an <edge>: choose that <edge>, and then choose their two additional <vertices>. The <variance of a sum> consequently gives the exact formula
$$
\operatorname{Var}T=\binom n3(p^3-p^6)+2\binom n2\binom{n-2}2(p^5-p^6).
$$
For sufficiently large $n$, the hypothesis $np\to\infty$ ensures $p>0$, so $\mu>0$. Dropping negative terms and simplifying the <binomial coefficients>,
$$
\frac{\operatorname{Var}T}{\mu^2}\leq\frac{1}{\binom n3p^3}+\frac{18(n-3)}{n(n-1)(n-2)p}
=O\!\left(\frac1{(np)^3}+\frac1{n^2p}\right)\longrightarrow0.
$$
Here $n^2p=n(np)\to\infty$ as well. The event $T\geq2\mu$ implies $|T-\mu|\geq\mu$. Applying the <Chebyshev inequality> from part (i) gives the requested conclusion:
$$
\boxed{\mathbb P\!\left(T\geq2p^3\binom n3\right)\leq\frac{\operatorname{Var}T}{\mu^2}\longrightarrow0.}
$$
Thus the <triangle count> is concentrated around its <expectation> throughout this range of the <binomial random graph>.
Back to article page
