Combinatorics: Frank Mousset, TAU, "The upper tail for triangles in sparse random graphs"

Speaker: Frank Mousset, TAU
Title: The upper tail for triangles in sparse random graphs
Let X denote the number of triangles in the random graph G(n,p) and consider the problem of determining the asymptotic behaviour of f_x(n,p) = log P[X > (1+x)E[X]] for a given positive constant x. Improving various earlier estimates, Chatterjee (2012) and DeMarco and Kahn (2012) independently proved that if np >> log(n), then f_x(n,p) = Theta(n^2p^2 log(1/p)). Since then, there has been considerable interest in determining the precise asymptotics of the (bounded) function c_x(n,p) = f_x(n,p)/(n^2p^2 log(1/p)). Partial results on this problem have been obtained by Chatterjee and Dembo (2014), Eldan (2016), Cook and Dembo (2018), and Augeri (2018) in various ranges of the density p. The most recent of these results, due to Augeri, determined the asymptotics of c_x(n,p) in the range where n^{-1/2} log^4(n) << p << 1. I will present a result that gives the asymptotics of c_x(n,p) in the larger range where n^{-1} log(n) << p << 1. Our proof relies on a simple variation on a classical moment argument due to Janson, Oleszkiewicz, and Ruciński (2004). I will also mention some related results for structures other than triangles. This is joint work with Matan Harel and Wojciech Samotij from Tel Aviv University.


Mon, 14/01/2019 - 11:00 to 13:00


Rothberg CS bldg, room B500, Safra campus, Givat Ram