On a problem of M. Talagrand. Issue 4 (26th February 2022)

• Record Type: Journal Article
• Authors: Frankston, Keith; Kahn, Jeff; Park, Jinyoung
• Is Part Of: Random structures & algorithms. Volume 61:Issue 4(2022)
• Page Start: 710
• Page End: 723
• Publication Date: 2022-02-26
• Subjects: expectation threshold -- fractional expectation threshold -- Kahn–Kalai Conjecture -- Talagrand conjectures -- threshold; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21077
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We address a special case of a conjecture of M. Talagrand relating two notions of "threshold" for an increasing family ℱ of subsets of a finite set V . The full conjecture implies equivalence of the "Fractional Expectation‐Threshold Conjecture, " due to Talagrand and recently proved by the authors and B. Narayanan, and the (stronger) "Expectation‐Threshold Conjecture" of the second author and G. Kalai. The conjecture under discussion here says there is a fixed L such that if, for a given ℱ, p ∈ [ 0, 1 ] admits λ : 2 V → ℝ + with ∑ S ⊆ F λ S ≥ 1 ∀ F ∈ ℱ, and ∑ S λ S p | S | ≤ 1 / 2 (a.k.a. ℱ is weakly p‐small ), then p / L admits such a λ taking values in { 0, 1 } ( ℱ is ( p / L ) ‐small ). Talagrand showed this when λ is supported on singletons and suggested, as a more challenging test case, proving it when λ is supported on pairs. The present work provides such a proof.