Thresholds versus fractional expectation-thresholds

Abstract

Proving a conjecture of Talagrand, a fractional version of the “expectation-threshold” conjecture of Kalai and the second author, we show that
$p_c \mathcal(F) = O(q_f (\mathcal{F}) \mathrm{log}\ell (\mathcal{F})$ for any increasing family $\mathcal{F}$ on a finite set $X$, where $p_c(\mathcal{F})$ and $q_f(\mathcal{F})$ are the threshold and “fractional expectation-threshold” of $\mathcal(F)$, and $\ell (\mathcal{F})$ is the maximum size of a minimal member of $\mathcal{F}$. This easily implies several heretofore difficult results and conjectures in probabilistic combinatorics, including thresholds for perfect hypergraph matchings (Johansson–Kahn–Vu), bounded degree spanning trees (Montgomery), and bounded degree graphs (new). We also resolve (and vastly extend) the “axial” version of the random multi-dimensional assignment problem (earlier considered by Martin–Mézard–Rivoire and Frieze–Sorkin). Our approach builds on a recent breakthrough of Alweiss, Lovett, Wu and Zhang on the Erdős–Rado “Sunflower Conjecture.”

Authors

Keith Frankston

Center For Communications Research - Princeton, Princeton, NJ

Jeff Kahn

Department of Mathematics, Rutgers University, Piscataway, NJ

Bhargav Narayanan

Department of Mathematics, Rutgers University, Piscataway, NJ

Jinyoung Park

Department of Mathematics, Stanford University, Stanford, CA