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

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!

Advertisements
This entry was posted in Combinatorics, Probability and tagged , , . Bookmark the permalink.

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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s