The ACO Seminar (2021–2022)

Let X denote the number of triangles in the random graph G(n,p). The problem of determining the asymptotic of the rate of the upper tail of X - that is, the function f_{n,p}(delta) = log Pr(X > (1+delta)E[X]) - has attracted considerable attention from both the combinatorics and probability communities. We will present a proof that, whenever log(n)/n << p << 1, the function f_{n,p}(c) = - [I(delta) + o(1)] n^2 p ^2 log(1/p), for an explicit function I(delta). This will demonstrate an approach for the study of the upper tail of behavior of "highly structured" nonlinear polynomials of Bernoulli random variables, where we expect the large deviation to be dominated by the appearance of small, dense structures. This is joint work with Frank Mousset and Wojciech Samotij.