A Bayesian Proof of the Spread Lemma
Elchanan Mossela b, Jonathan Weedc d, Nike Suna b, Ilias Zadika b e f✉
- aDepartment of Mathematics Massachusetts Institute of Technology Cambridge Massachusetts USA
- bDepartment of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA
- cCenter for Data Science and Courant Institute of Mathematical Sciences New York University New York New York USA
- dCenter for Data Science and Courant Institute of Mathematical Sciences, New York University, New York, New York, USA
- eDepartment of Statistics and Data Science Yale University New Haven Connecticut USA
- fDepartment of Statistics and Data Science, Yale University, New Haven, Connecticut, USA
- ✉Corresponding author
Papers open inside SciRah from the original publisher or repository; SciRah never hosts them.
Abstract
ABSTRACT A key set‐theoretic “spread” lemma has been central to two recent celebrated results in combinatorics: the recent improvements on the sunflower conjecture by Alweiss, Lovett, Wu, and Zhang; and the proof of the fractional Kahn–Kalai conjecture by Frankston, Kahn, Narayanan, and Park. In this work, we present a new proof of the spread lemma, that—perhaps surprisingly—takes advantage of an explicit recasting of the proof in the language of Bayesian inference. We show that from this viewpoint the reasoning proceeds in a straightforward and principled probabilistic manner, leading to a truncated second moment calculation which concludes the proof.