Past exam of the mathematics course of the University of Cambridge / 2016 / ia / Paper 2 / 12F (Probability)

For each unordered triple of distinct vertices, let $I_A$ be the indicator variable that its three edges are present. This is a binomial random graph, so edge independence gives $\mathbb{E}[I_A]=p^3$. The triangle count in a binomial random graph is $T={\sum }_A{I}_A$. There are $\left(\genfrac{}{}{0ex}{}{n}{3}\right)$ such triples; all are triangles in the complete graph.

The combinatorial maximum and expectation areThe maximum is attainable with positive probability if $p>0$; for $p=0$, the random variable is identically zero. The linearity of expectation requires no independence between different triangle indicators.

The Markov inequality states that for a nonnegative random variable $Z$ and $a>0$,Because $T$ is integer-valued, apply it with $a=1$. With $p=n^{-\alpha }$,ThereforeThis is the first moment method: if the expected triangle count in a binomial random graph tends to zero, triangles occur with vanishing probability.

The Chebyshev inequality states that for a random variable $Z$ with finite variance and $a>0$,Write ${\mu }_n=\mathbb{E}[T]$. The ratio in the hypothesis presupposes ${\mu }_n>0$ for all sufficiently large $n$. On the event $T=0$, the deviation from the mean equals ${\mu }_n$. Thus the Chebyshev inequality with $a={\mu }_n$ givesThis is the second moment method. It uses only the stipulated relative variance bound; no assumption that triangle indicators are independent is needed.