Plurality is stablest conjecture, discrete version
Let , let , and let . For a function , write for the influence of coordinate on component , and let denote its total noise stability. Let be the standard basis vectors and let be the plurality function, with ties mapped to . Plurality is stablest conjecture, discrete version. There exists such that, whenever for every and ,
This is the formal low-influence, equal-outcome-probability version of the voting claim and would identify plurality as asymptotically optimal for noise stability; it remains open in the full stated range.
References
4 papers in this index state this conjecture (2019–2022). The statement above is taken from the most recent of them; the others are arXiv:2011.05583, arXiv:2006.05460, arXiv:1901.03934.
Source: Steven Heilman, “Hyperstable Sets with Voting and Algorithmic Hardness Applications”, arXiv:2209.11216 (2022).
Progress summary
The conjecture remains open, with plurality proved optimal only for two candidates and for three candidates at sufficiently small positive noise.
The conjecture, originating in work of Khot, Kindler, Mossel, and O’Donnell (2005), asserts that among low-influence voting rules with equal outcome probabilities, plurality maximizes noise stability. The unrestricted unequal-probability analogue is false, but that does not affect this equal-probability formulation.
Known results
- : the conjecture is the Majority is Stablest theorem (Mossel, O’Donnell, and Oleszkiewicz, 2010).
- : proved for all dimensions and sufficiently small (Heilman and Tarter, 2021).
- The equal-expectation assumption is necessary in general for (Heilman, Mossel, and Neeman, 2016).
- The regime was known previously, but not the full range of and .
2021 three-candidate partial proof
Heilman and Tarter proved the conjecture for and sufficiently small positive correlations, uniformly in the dimension. This is a genuine partial advance, but the full conjecture for arbitrary and the complete correlation range remains unresolved; the later hyperstability work presents a strategy rather than a proof.
Current status (as of November 2026): The cases , with sufficiently small positive , and the previously known near- regime are settled; the full equal-probability conjecture remains open.
Sources
Solutions 0
No solutions have been posted yet.