= Clique-packing amplification of moment bounds
{title2=$\Pr(Z_k=0)\le\exp(-c m^2/k^8)$}
Let $X$ count $k$-<cliques> in a <binomial random graph> on $m$ <vertices> and $Y$ count distinct ordered pairs sharing an <edge>. The <clique conflict graph> gives $Z_k\ge X^2/(X+Y)$: order its <vertices> randomly and keep each one preceding all its neighbours, then apply the <Cauchy-Schwarz inequality>. Another application gives $\mathbb EZ_k\ge(\mathbb EX)^2/(\mathbb EX+\mathbb EY)$. If $\mathbb EY/(\mathbb EX)^2=O(k^4/m^2)$ and $1/\mathbb EX$ is no larger, then $\mathbb EZ_k=\Omega(m^2/k^4)$. Changing one <edge> changes $Z_k$ by at most one, so the <Azuma-Hoeffding inequality> for an <edge-exposure martingale> yields the displayed exponential absence bound. This supports a <union bound> over exponentially many adaptive candidate subsets.
Back to article page
