Combinatorics Seminar

When: Sunday, October 28, 10am
Where: Schreiber 309
Speaker: Frank Mousset, Tel Aviv University
Title: The upper tail for triangles in sparse random graphs

Abstract:

Let $X$ denote the number of triangles in the random graph $G(n,p)$, and consider the problem of determining the asymptotics of the function $f_x(n,p) =\log P[X \gt (1+x)E[X]]$ for a given positive constant $x$. I will present a proof of the fact that for all $p=p(n)$ such that $polylog(n)/n \ll p \ll 1$, one has $f_x(n,p) = (1+o(1)) c(x) n^2p^2 \log p$ for an explicit function $c(x$). So far, this was only known when $p\gg n^{-1/18} \log n$ (Lubetzky and Zhao 2014, Eldan 2016).

This is joint work with Matan Harel and Wojciech Samotij.