Thresholds versus fractional expectation-thresholds
share
Proving a conjecture of Talagrand, a fractional version of the 'expectation-threshold' conjecture of Kalai and the second author, we show for any increasing family F on a finite set X that p_c (F) =O( q_f (F) logℓ(F)), where p_c(F) and q_f(F) are the threshold and 'fractional expectation-threshold' of F, and ℓ(F) is the largest size of a minimal member of F. This easily implies various heretofore difficult results in probabilistic combinatorics, e.g. thresholds for perfect hypergraph matchings (Johansson-Kahn-Vu) and bounded-degree spanning trees (Montgomery). We also resolve (and vastly extend) one version of the 'random multi-dimensional assignment' problem of Frieze and Sorkin. Our approach builds on recent breakthrough work of Alweiss, Lovett, Wu and Zhang on the Erdős-Rado 'sunflower' conjecture.
READ FULL TEXT