pith. sign in

arxiv: 1005.4471 · v2 · pith:5BC4CI4Cnew · submitted 2010-05-25 · 🧮 math.PR · math.CO

Upper tails for triangles

classification 🧮 math.PR math.CO
keywords trianglesenyigraphnumberrandomsometailstight
0
0 comments X
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.