The upper tail for triangles in sparse random graphs

The upper tail for triangles in sparse random graphs

-
Wojtek Samotij, Tel Aviv University
Fine Hall 214

Let $X$ denote the number of triangles in the binomial random graph $G(n,p)$. The problem of determining the logarithmic upper tail probability of $X$, that is, the function $f(n,p,c) = \log Pr(X > (1+c)E[X])$, has attracted considerable attention of both the combinatorics and the probability communities. We shall present a proof of the fact that, whenever $log(n) / n \ll p \ll 1$, then $f(n,p,c) = r(c) n^2 p^2 log(p)$ for an explicit function $r(c)$. This is joint work with Matan Harel and Frank Mousset.