Binomial sampling gap for independence ratio

Conjecture 2.9 · arXiv:2208.06858

arXiv Conjecture high confidence— first stated 2023-08-21

Authors: Noga Alon, Ehud Friedgut, Gil Kalai, Guy Kindler

Status partial medium confidence

Conjecture 2.9 asserts that for every graph $G$ on $n$ vertices with independence number $\alpha n$ ($\alpha < 1/2$), the expected size of the maximal independent set in a binomial random half-subset satisfies $\alpha^{**}(G) \leq \alpha - \varepsilon^{**}(\alpha)$ for some positive $\varepsilon^{**}(\alpha)$ depending only on $\alpha$. The source paper itself establishes the conjecture for $\alpha > 1/4$ (Theorem 2.10) and for regular graphs when $\alpha > 1/8$ (Theorem 2.11), leaving the full range $(0, 1/4]$ for general graphs open. Semantic Scholar lists five citing papers (to May 2026), none of which could be verified to make further progress on this specific conjecture; the closest follow-ups concern the hat-puzzle side of the paper or the related Bollobás–Erdős–Tuza conjecture.

Reviewer notes. Semantic Scholar returns five citing papers (arXiv:2503.09042, arXiv:2405.18264, arXiv:2404.01639, arXiv:2405.18264 duplicate, and one without an arXiv ID); WebFetch of 2503.09042 ('A Fourier approach to Levine's hat puzzle', Heilman–Tamuz 2025) confirmed it addresses the two-player hat puzzle via Boolean harmonic analysis, not Conjecture 2.9 on independent sets; WebFetch of 2405.18264 (Cheng–Xu 2024) confirmed it concerns the Bollobás–Erdős–Tuza conjecture for $K_{s,t}$-free graphs and does not address Conjecture 2.9 directly. No paper found that resolves the conjecture for $\alpha \in (0, 1/4]$ on general graphs.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. $\varepsilon^{**}(\alpha) > 0$ for all $\alpha \in (0, 1/2)$. In other words, there exists a monotone non-decreasing function $\varepsilon^{**} : (0,1/2) \to (0,1/2)$ such that the following holds: if $G$ is a graph on $n$ vertices with maximum independent set of size $\alpha n$, $W$ is a binomial random subset of $V(G)$, and $I_W$ is the maximal independent set contained in $W$, then $$\alpha^{**}(G) = E_W\!\left[|I_W|/n\right] \leq \alpha - \varepsilon^{**}(\alpha).$$

Context

This is the special case of Conjecture 2.8 where the random-subset distribution is simply binomial (each vertex included independently with probability $1/2$), which the authors describe as 'a fundamental problem in the study of independent sets in graphs'. The paper proves this for $\alpha > 1/4$ (Theorem 2.10) and for regular graphs with $\alpha > 1/8$ (Theorem 2.11).

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