Upper tails for triangles
classification
🧮 math.PR
math.CO
keywords
trianglesenyigraphnumberrandomsometailstight
read the original abstract
With $\xi$ the number of triangles in the usual (Erd\H{o}s-R\'enyi) random graph $G(m,p)$, $p>1/m$ and $\eta>0$, we show (for some $C_{\eta}>0$) $$\Pr(\xi> (1+\eta)\E \xi) < \exp[-C_{\eta}\min{m^2p^2\log(1/p),m^3p^3}].$$ This is tight up to the value of $C_{\eta}$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.