← All problems

Plurality is stablest conjecture, discrete version

7 years old · traced to

Let m≥2m\geq 2, let ρ∈[0,1]\rho\in[0,1], and let ε>0\varepsilon>0. For a function f:{1,…,m}n→Δmf:\{1,\ldots,m\}^n\to\Delta_m, write Inf⁡i(fj)\operatorname{Inf}_i(f_j) for the influence of coordinate ii on component fjf_j, and let SρfS_\rho f denote its total noise stability. Let e1,…,eme_1,\ldots,e_m be the standard basis vectors and let PLUR⁡m,n\operatorname{PLUR}_{m,n} be the plurality function, with ties mapped to m−1∑i=1meim^{-1}\sum_{i=1}^m e_i. Plurality is stablest conjecture, discrete version. There exists τ>0\tau>0 such that, whenever Inf⁡i(fj)≤τ\operatorname{Inf}_i(f_j)\leq\tau for every i,ji,j and Ef=m−1∑i=1mei\mathbb{E}f=m^{-1}\sum_{i=1}^m e_i,

Sρf≤lim⁡n→∞SρPLUR⁡m,n+ε.S_\rho f\leq\lim_{n\to\infty}S_\rho\operatorname{PLUR}_{m,n}+\varepsilon.

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

Refreshed
Open · progress reported

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

  • m=2m=2: the conjecture is the Majority is Stablest theorem (Mossel, O’Donnell, and Oleszkiewicz, 2010).
  • m=3m=3: proved for all dimensions and sufficiently small ρ>0\rho>0 (Heilman and Tarter, 2021).
  • The equal-expectation assumption is necessary in general for m≥3m\geq 3 (Heilman, Mossel, and Neeman, 2016).
  • The regime ρ→1−\rho\to 1^- was known previously, but not the full range of mm and ρ\rho.

2021 three-candidate partial proof

Heilman and Tarter proved the conjecture for m=3m=3 and sufficiently small positive correlations, uniformly in the dimension. This is a genuine partial advance, but the full conjecture for arbitrary m≥3m\geq 3 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 m=2m=2, m=3m=3 with sufficiently small positive ρ\rho, and the previously known near-11 regime are settled; the full equal-probability conjecture remains open.

Sources

Solutions 0

No solutions have been posted yet.