= Growing-clique overlap bound
{title2=$r\leq n^{1/3},\ \mu_r\to\infty,\ \mu_{r+1}\to0\Longrightarrow\operatorname{Var}X_r=o(\mu_r^2)$}
Write $\mu_r=\binom nrp^{\binom r2}$ and $T_s=\binom rs\binom{n-r}{r-s}p^{-\binom s2}/\binom nr$. The first mean condition implies $p^{-1}\leq(en/r)^{2/(r-1)}$ eventually. For $2\leq s\leq r/2$, this yields $T_s\leq(C/s)^s$, and each fixed-$s$ term tends to zero when $n\geq r^3$. The second mean condition implies $p\leq((r+1)/n)^{2/r}$ eventually. Writing $s=r-j$ gives $T_{r-j}=\mu_r^{-1}\binom rj\binom{n-r}j p^{j(2r-j-1)/2}\leq\mu_r^{-1}(C/j)^j$ for $1\leq j\leq r/2$, and $T_r=\mu_r^{-1}$. Both bounding series are summable. The <overlap formula for the variance of a clique count> therefore gives relative variance tending to zero; the <second moment method> proves an $r$-<clique> exists <with high probability>.
Back to article page
