= Triangle variance in a binomial random graph
{title2=$\operatorname{Var}X=\binom n3p^3(1-p^3)+12\binom n4p^5(1-p)$}
For the <triangle count> in a <binomial random graph>, distinct triangle indicators are independent unless they share an <edge>. A shared-edge pair has <covariance> $p^5(1-p)$, and there are $12\binom n4$ ordered pairs of that type. The individual indicator variances give the first term. Equivalently,
$$
\mathbb EX^2=\binom n3\sum_{\ell=0}^3\binom3\ell\binom{n-3}{3-\ell}p^{6-\binom\ell2},
$$
by counting ordered pairs according to the number of shared <vertices>.
Back to article page
