Upper tails for triangles

Bobby DeMarco, Jeff Kahn

With $\xi$ the number of triangles in the usual (Erdős-Rényi) random graph $G(m,p)$, $p>1/m$ and $\eta >0$, we show (for some $C_{\eta }>0$) $$\Pr(ξ> (1+η)\E ξ) < \exp[-C_η\min{m^2p^2\log(1/p)…