Non-existence probabilities and lower tails via Gibbs uniqueness on hypertrees

Given a graph $H$, what is the probability that $G(n,p)$ contains no copy of $H$ or fewer copies than expected? This is a canonical example of a `lower-tail’ large deviation probability that arises naturally in combinatorics. Other examples include the probability that a random subset of $[n]$ avoids $k$-term arithmetic progressions or that a random subset of an abelian group is sum free.

In this talk, I will discuss a method for determining the logarithmic asymptotics (or rate function) for such probabilities. The method applies for a range of parameters in the `critical regime’: between the regime amenable to hypergraph container methods and that amenable to Janson’s inequality.

The method works in the general framework of estimating the probability that a $p$-random subset of vertices of a $k$-uniform hypergraph contains fewer hyperedges than expected. We show that under some simple structural conditions on the hypergraph and an upper bound on $p$ determined by a phase transition on an infinite hypertree, this probability can be approximated by a formula derived from a Gibbs measure on the hypertree.

This is joint work with Will Perkins, Aditya Potukuchi and Michael Simkin.

For information about the Richard P. Stanley Seminar in Combinatorics, visit https://math.mit.edu/combin/