论文标题
第二刻证明散布引理
A second moment proof of the spread lemma
论文作者
论文摘要
本说明涉及一个众所周知的结果，我们将``扩散引理''称为``扩散引理''，该结果在随机集合中建立了所需结构的存在（概率很高）。传播引理是最近两个庆祝结果的核心：（a）Alweiss，Lovett，Wu和Zhang（2019）在Erdős-Rado Sunflower猜想中的改善； （b）弗兰克斯顿，卡恩，纳拉亚南和帕克（2019）的Kalai猜想的分数证明。虽然首先通过精致的计数论点证明了引理（后来是完善的），但通过香农的无声编码定理（Rao，2019年）以及Shannon Entropy Bounds的操纵（Tao，Tao，2020年），也给出了其他证据。 在本说明中，我们提供了扩散引理的新证明，该证明利用了贝叶斯统计推断的语言的明确重塑证明。我们表明，从这个角度来看，证明以一种直接而有原则的概率方式进行，导致第二刻计算得出结论，从而结束了证明。该证明也可以看作是Achlioptas和Coga-Oghlan（2008）在研究随机约束满意度问题的研究中引入的``种植技巧''的演示。
This note concerns a well-known result which we term the ``spread lemma,'' which establishes the existence (with high probability) of a desired structure in a random set. The spread lemma was central to two recent celebrated results: (a) the improved bounds of Alweiss, Lovett, Wu, and Zhang (2019) on the Erdős-Rado sunflower conjecture; and (b) the proof of the fractional Kahn--Kalai conjecture by Frankston, Kahn, Narayanan and Park (2019). While the lemma was first proved (and later refined) by delicate counting arguments, alternative proofs have also been given, via Shannon's noiseless coding theorem (Rao, 2019), and also via manipulations of Shannon entropy bounds (Tao, 2020). In this note we present a new proof of the spread lemma, that takes advantage of an explicit recasting of the proof in the language of Bayesian statistical inference. We show that from this viewpoint the proof proceeds in a straightforward and principled probabilistic manner, leading to a truncated second moment calculation which concludes the proof. The proof can also be viewed as a demonstration of the ``planting trick'' introduced by Achlioptas and Coga-Oghlan (2008) in the study of random constraint satisfaction problems.
