On a problem of M. Talagrand

Abstract

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\in [0,1]$ admits $\lambda :2^V\to {\mathbb{R}}^{+}$ with \[ \mbox{${\sum }_{S\subseteq F}{\lambda }_S\ge 1\forall F\in \mathcal{F}$} \] and \[ \mbox{${\sum }_S{\lambda }_S{p}^{|S|}\le 1/2$} \] (a.k.a. $\mathcal{F}$ is weakly $p$-small), then $p/L$ admits such a $\lambda$ taking values in $\{0,1\}$ ($\mathcal{F}$ is $(p/L)$-small). Talagrand showed this when $\lambda$ is supported on singletons and suggested, as a more challenging test case, proving it when $\lambda$ is supported on pairs. The present work provides such a proof.

11 pages