2021/05/23 by Frankston, Keith, Kahn, Jeff, Park, Jinyoung · 1 citation
#05C99 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2105.10905
We address a special case of a conjecture of M. Talagrand relating two notions of "threshold" for an increasing family \mathcal F 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 \mathcal F, p∈ [0,1] admits λ:2V → \mathbb R+ with \mbox∑S⊆ FλS≥ 1 ~~∀ F∈ \mathcal F and \mbox∑SλSp|S| ≤ 1/2 (a.k.a. \mathcal F is weakly p-small), then p/L admits such a λ taking values in \0,1\ (\mathcal F 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.