Thresholds versus fractional expectation-thresholds

Keith Frankston, Jeff Kahn, Bhargav Narayanan, Jinyoung Park

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

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

Original languageEnglish (US)
Pages (from-to)475-495
Number of pages21
JournalAnnals of Mathematics
Volume194
Issue number2
DOIs
StatePublished - Sep 2021
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Keywords

  • Expectation thresholds
  • Random assignment problem
  • Thresholds

Fingerprint

Dive into the research topics of 'Thresholds versus fractional expectation-thresholds'. Together they form a unique fingerprint.

Cite this