EUVIMEDEUVIMED entdecken
Crossref

Thresholds versus fractional expectation-thresholds

Keith Frankston, Jeff Kahn, Bhargav Narayanan, Jinyoung Park

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

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →