Matan Harel, Frank Mousset, and Wojciech Samotij and the “the infamous upper tail” problem

Combinatorics and more 2019-08-20

Let me report today on a major breakthrough in random graph theory and probabilistic combinatorics. Congratulations to Matan, Frank, and Vojtek!

Artist: Heidi Buck. “Catch a Dragon by the Tail 2” ( source )

Upper tails via high moments and entropic stability by Matan Harel, Frank Mousset, and Wojciech Samotij

Abstract:

Suppose that X is a bounded-degree polynomial with nonnegative coefficients on the p-biased discrete hypercube. Our main result gives sharp estimates on the logarithmic upper tail probability of X whenever an associated extremal problem satisfies a certain entropic stability property. We apply this result to solve two long-standing open problems in probabilistic combinatorics: the upper tail problem for the number of arithmetic progressions of a fixed length in the p-random subset of the integers and the upper tail problem for the number of cliques of a fixed size in the random graph $G_{n,p}$ . We also make significant progress on the upper tail problem for the number of copies of a fixed regular graph H in $G_{n,p}.$ To accommodate readers who are interested in learning the basic method, we include a short, self-contained solution to the upper tail problem for the number of triangles in $G_{n,p}$ for all p=p(n) satisfying $\frac {\log n}{n}$ $\ll$ $p \ll 1$ .

The introduction does a very nice job of presenting the rich history of the problem. Here is a 2002 paper by Svante Janson and Andrzej Ruciński on the infamous upper tail. (And a lot has happened since then with regard to this problem and on non linear large deviation theory). Following, there is a lovely section with a short solution for the case of triangles.

Forthcoming reference [48] talks about lower tails! Stay tuned!