Thresholds versus fractional expectation-thresholds
Annals of Mathematics · 01.09.2021 · 194 (2) · 475-495
DOI: 10.4007/annals.2021.194.2.2 ↗Kurz gefasst
Fachartikel in der Zeitschrift Annals of Mathematics, erschienen am 01.09.2021. Verfasst von Keith Frankston und 3 weiteren Autor:innen. Die Arbeit wurde bisher 61-mal zitiert (Crossref).
Abstract (Originalsprache)
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."
Zitieren
APA
Frankston, K., Kahn, J., Narayanan, B., & Park, J. (2021). Thresholds versus fractional expectation-thresholds. Annals of Mathematics, 194(2), 475-495. https://doi.org/10.4007/annals.2021.194.2.2
Vancouver
Frankston K, Kahn J, Narayanan B, Park J. Thresholds versus fractional expectation-thresholds. Annals of Mathematics. 2021;194(2):475-495. doi:10.4007/annals.2021.194.2.2
BibTeX
@article{Frankston2021,
author = {Frankston, Keith and Kahn, Jeff and Narayanan, Bhargav and Park, Jinyoung},
title = {Thresholds versus fractional expectation-thresholds},
journal = {Annals of Mathematics},
year = {2021},
volume = {194},
number = {2},
pages = {475--495},
doi = {10.4007/annals.2021.194.2.2}
}
EUVIMED