= Overlap formula for the variance of a clique count
{title2=$\operatorname{Var}X/(\mathbb EX)^2$}
For the number $X$ of $k$-<cliques> in a <binomial random graph> $G(n,p)$, with $0<p<1$ and $\mu=\mathbb EX$,
$$
\frac{\operatorname{Var}X}{\mu^2}=\sum_{j=2}^k\frac{\binom kj\binom{n-k}{k-j}}{\binom nk}\left(p^{-\binom j2}-1\right).
$$
Two $k$-sets overlapping in $j$ vertices share $\binom j2$ edges. Overlaps of zero or one vertex give independent indicators; $j=k$ includes the diagonal terms. The identity is useful for the <second moment method>.
Back to article page
