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 . We also make significant progress on the upper tail problem for the number of copies of a fixed regular graph *H* in 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 for all *p=p(n)* satisfying .

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!

### Like this:

Like Loading...

*Related*

Pingback: Equiangular lines with a fixed angle and other breakthroughs from Yufei Zhao’s blog | Combinatorics and more