TY - JOUR
T1 - Thresholds versus fractional expectation-thresholds
AU - Frankston, Keith
AU - Kahn, Jeff
AU - Narayanan, Bhargav
AU - Park, Jinyoung
N1 - Funding Information:
by NSF grant DMS-1501962 and BSF Grant 2014290. The third author was supported by NSF grant DMS-1800521.
Publisher Copyright:
© 2021. Department of Mathematics, Princeton University.
PY - 2021/9
Y1 - 2021/9
N2 - Proving a conjecture of Talagrand, a fractional version of the "expectation-threshold" conjecture of Kalai and the second author, we show that (Formula Presented) for any increasing family F on a finite set X, where pc(F) and qf (F) are the threshold and "fractional expectation-threshold" of F, and l(F) is the maximum size of a minimal member of 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-Mezard-Rivoire and Frieze{Sorkin). Our approach builds on a recent breakthrough of Alweiss, Lovett, Wu and Zhang on the Erdos-Rado "Sun ower Conjecture."
AB - Proving a conjecture of Talagrand, a fractional version of the "expectation-threshold" conjecture of Kalai and the second author, we show that (Formula Presented) for any increasing family F on a finite set X, where pc(F) and qf (F) are the threshold and "fractional expectation-threshold" of F, and l(F) is the maximum size of a minimal member of 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-Mezard-Rivoire and Frieze{Sorkin). Our approach builds on a recent breakthrough of Alweiss, Lovett, Wu and Zhang on the Erdos-Rado "Sun ower Conjecture."
KW - Expectation thresholds
KW - Random assignment problem
KW - Thresholds
UR - http://www.scopus.com/inward/record.url?scp=85117394301&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85117394301&partnerID=8YFLogxK
U2 - 10.4007/annals.2021.194.2.2
DO - 10.4007/annals.2021.194.2.2
M3 - Article
AN - SCOPUS:85117394301
VL - 194
SP - 475
EP - 495
JO - Annals of Mathematics
JF - Annals of Mathematics
SN - 0003-486X
IS - 2
ER -