Abstract
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.