Upper Tails for Cliques

With $ξ_{k}=ξ_{k}^{n,p}$ the number of copies of $K_k$ in the usual (Erdős-Rényi) random graph $G(n,p)$, $p\geq n^{-2/(k-1)}$ and $η>0$, we show when $k>1$ $$\Pr(ξ_k> (1+η)\E ξ_k) < \exp [-\gO_{η,k} \min\{n^2p^{k-1}\log(1/p), n^kp^{\binom{k}{2}}\}].$$ This is tight up to the value of the constant in the exponent.

No reviews yet.

No comments yet.