Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 36 / 3

Each unordered triple of vertices is a triangle in a graph with probability $p^3$. Consequently the triangle count in a binomial random graph satisfies $\mathbb{E}X=\left(\genfrac{}{}{0ex}{}{n}{3}\right)p^3\le (np{)}^3/6$. If $np\to 0$, the Markov inequality gives $\mathbb{P}(X>0)\le \mathbb{E}X\to 0$. Hencethe sparse direction of the triangle-existence threshold in a binomial random graph.

Count each unordered triple once. For a three-element vertex set $S$, let $I_S$ indicate that its three edges are present. Then $X={\sum }_{|S|=3}{I}_S$ andIf $|S\cap T|=\ell$, their edge sets have $\left(\genfrac{}{}{0ex}{}{\ell }{2}\right)$ edges in common, so their union contains $6-\left(\genfrac{}{}{0ex}{}{\ell }{2}\right)$ distinct edges. Independence gives $\mathbb{E}[I_S{I}_T]=p^{6-\left(\genfrac{}{}{0ex}{}{\ell }{2}\right)}$. There are $\left(\genfrac{}{}{0ex}{}{n}{3}\right)\left(\genfrac{}{}{0ex}{}{3}{\ell }\right)\left(\genfrac{}{}{0ex}{}{n-3}{3-\ell }\right)$ such ordered pairs: choose $S$, its shared vertices, and the remaining vertices of $T$. ThusThis overlap count is the basis of triangle variance in a binomial random graph.

When $\mu =\mathbb{E}X>0$, the event $X=0$ implies $|X-\mu |\ge \mu$. The Chebyshev inequality therefore givesThis is the second moment method for proving that a nonnegative count is positive.

Two distinct triangles in a graph with at most one common vertex use disjoint edges, so their indicator random variables are independent and have zero covariance. A pair sharing an edge has covariance $p^5-p^6$. The count from part (i) givesWith $\mu =\left(\genfrac{}{}{0ex}{}{n}{3}\right)p^3$, the triangle variance in a binomial random graph therefore satisfiesBoth terms tend to zero when $np\to \infty$, because $n^{2}p=n(np)\to \infty$. Applying part (ii) provescompleting the triangle-existence threshold in a binomial random graph.