Probabilistic and game thresholds

Abstract

Let $X$ be a finite set and $\mathcal{F}\subseteq 2^X$ a non-trivial increasing property. We show that the bias-threshold $b(\mathcal{F})$ for the Picker-Chooser $\mathcal{F}$-game satisfies $b(\mathcal{F})\ge \alpha /p_c(\mathcal{F})$, where $p_c(\mathcal{F})$ is the threshold for the property $\mathcal{F}$ and $\alpha >0$ is an absolute constant. This proves that Picker-Chooser games satisfy one-sided ``probabilistic intuition''. The proof is based on the notion of influence from the theory of boolean functions.

arXiv comment12 pages