Positive gap in hat-problem success probability
Conjecture 2.8 · arXiv:2208.06858
Status open high confidence
Conjecture 2.8 states that ε*(α) > 0 for all α ∈ (0, 1/2), where ε*(α) measures a positivity gap between the fractional independence ratio α*(G) and the independence ratio ᾱ(G) under a Bernoulli(1/2)-marginal random-subset distribution. No paper resolving this conjecture was found. A related but distinct conjecture of Friedgut–Kalai–Kindler (about hitting sets for maximum independent sets) was disproved by Alon in arXiv:2103.05998, but that paper predates arXiv:2208.06858 and addresses a different statement.
Reviewer notes. Conjecture 2.8 (ε*(α) > 0 for all α ∈ (0,1/2)) is the strongest of the three conjectures in §2: it implies Conjecture 2.6 which implies Levine's conjecture. The related conjecture about small hitting sets for maximum independent sets (Conjecture 1.1 in arXiv:2103.01541, which overlaps with this paper) was disproved by Alon in arXiv:2103.05998, but Conjecture 2.8 about ε*(α) is a separate and harder positivity statement. The source paper was published as SIAM J. Discrete Math. (DOI: 10.1137/22M1515975). No resolution of Conjecture 2.8 was found in the literature up to May 2026.
Context
Here $\varepsilon^*(\alpha) = \inf_{G:\,\bar{\alpha}(G)\geq\alpha}(\bar{\alpha}(G) - \alpha^*(G))$, where $\alpha^*(G)$ is defined via an optimal partition of $V(G)^r$ and a positively-correlated random-subset distribution with Bernoulli$(1/2)$ marginals. This conjecture would imply Conjecture 2.6 and hence Levine's conjecture.
Notes. PDF source — some definitions in Section 2.4 rely on notation that may be partially garbled; the conjecture statement itself is clearly readable.
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