Upper Tails for Cliques

Bobby DeMarco, Jeff Kahn

With ${\xi }_k={\xi }_k^{n,p}$ the number of copies of $K_k$ in the usual (Erdős-Rényi) random graph $G(n,p)$, $p\ge n^{-2/(k-1)}$ and $\eta >0$, we show when $k>1$ $$\Pr(ξ_k> (1+η)\E ξ_k)…