Graph-theory open problems

Vanishing success probability for monotone hat strategies

AX_levine_hat_monotone_success_vanishes

Source: arXiv:2208.06858 — The success probability in Levine's hat problem, and independent sets in graphs

Conjecture 2.2 · arXiv:2208.06858

arXiv Conjecture high confidence— first stated 2023-08-21
Authors: Noga Alon, Ehud Friedgut, Gil Kalai, Guy Kindler

Status ai-disproved high confidence

A block-tribes construction gives balanced monotone strategies with success probability arbitrarily close to 1/2 for every number of players, so in fact p_monotone(t)=1/2.

Auto-reviewed 2026-08-31 with gpt-5.6-sol.

AI-generated write-up ai-disproved

Open the PDF write-up

This is a model-generated research artifact, not a peer-reviewed publication or a formally verified proof.

Conjecture. $p_{\mathrm{monotone}}(t)$ tends to $0$ as $t$ grows.

Context

This is progressively stronger than Conjecture 2.1, as $p_{\mathrm{monotone}}(t) \geq p_{\mathrm{intersecting}}(t) \geq p_{\mathrm{dict}}(t)$, where winning sets are all balanced monotone families on $\{0,1\}^n$. The authors describe these two conjectures as 'progressively stronger than Conjecture 1.1'.

Source paper

The success probability in Levine's hat problem, and independent sets in graphs
Noga Alon, Ehud Friedgut, Gil Kalai, Guy Kindler · 2023-08-21
https://arxiv.org/abs/2208.06858 PDF source

Related conjectures

  • implies Vanishing hat-success probability for intersecting families open Hypothesis-class containment: intersecting winning families are among the balanced monotone families, giving the pointwise inequality p_monotone(t) ≥ p_intersecting(t) ≥ p_dict(t), which the paper states explicitly (both contexts). If the larger quantity p_monotone(t) tends to 0, the sandwiched nonnegative quantity p_intersecting(t) must also tend to 0. Direction correct: Conjecture 2.2 (monotone) is the stronger statement, as the paper itself says ('progressively stronger').

View in the relation graph — relations are AI-reviewed, not formally verified.