Probabilistic and game thresholds
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 α/ p_c(\mathcal{F})$, where $p_c(\mathcal{F})$ is the threshold for the property $\mathcal{F}$ and $α> 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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.30730
curl -X POST /api/v1/records/arxiv/2610.30730/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.30730/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'