Thresholds Versus Fractional Expectation-Thresholds

Given an increasing family F in {0,1}^n, its measure according to mu_p increases and often exhibits a threshold behavior, growing quickly as p increases from near 0 to near 1 around a specific value p_c. Thresholds of families have been of great historical interest and a central focus of the study of random discrete structures (e.g. random graphs and hypergraphs), with estimation of thresholds for specific properties the subject of some of the most challenging work in the area.

In 2006, Kahn and Kalai conjectured that a natural (and often easy to calculate) lower bound q(F) (which we refer to as the “expectation-threshold”) for the threshold is in fact never far from its actual value. We prove a fractional version (proposed by Talagrand) of this so called “expectation-threshold” conjecture showing that for any increasing family we have p_c(F) = O(q_f(F) log \ell(F)), where q_f is the “fractional expectation-threshold” and \ell(F) is the maximum size of a minimal element of F.

This result easily implies several previously difficult results in probabilistic combinatorics such as thresholds for perfect hypergraph matchings (Johansson–Kahn–Vu) and bounded-degree spanning trees (Montgomery). Our approach builds on a recent breakthrough of Alweiss, Lovett, Wu and Zhang on the Erdős–Rado “Sunflower Conjecture.”

This is joint work with Jeff Kahn, Bhargav Narayanan, and Jinyoung Park.