Plurality is Stablest conjecture for kk candidates

From papers

For k2k\geq 2, let f ⁣:{1,,k}nΔkf\colon\{1,\ldots,k\}^{n}\to\Delta_{k}, where Δk\Delta_k is the probability simplex, and let Infi(fj)\operatorname{Inf}_{i}(f_j) denote the influence of coordinate ii on the jjth coordinate function. Define the noise stability by Sρf=j=1kSρfjS_\rho f=\sum_{j=1}^{k}S_\rho f_j, and let PLURk,n\mathrm{PLUR}_{k,n} be the plurality function, with ties mapped to the uniform vector 1kj=1kej\frac1k\sum_{j=1}^{k}e_j. For every ρ[1/(m1),1]\rho\in[-1/(m-1),1] and ε>0\varepsilon>0, there is τ>0\tau>0 such that the following holds for every ff satisfying Infi(fj)τ\operatorname{Inf}_{i}(f_j)\leq\tau for all ii and jj.

Plurality is Stablest conjecture. If ρ0\rho\geq0 and Ef=1kj=1kej\mathbb{E}f=\frac1k\sum_{j=1}^{k}e_j, then

SρflimnSρPLURk,n+ε.S_\rho f\leq\lim_{n\to\infty}S_\rho\mathrm{PLUR}_{k,n}+\varepsilon.

If 1/(m1)ρ<0-1/(m-1)\leq\rho<0, then

SρflimnSρPLURk,nε.S_\rho f\geq\lim_{n\to\infty}S_\rho\mathrm{PLUR}_{k,n}-\varepsilon.

This is the formal discrete Plurality is Stablest statement cited as the source of the three-candidate conjecture and as the conjectural ingredient for sharp MAX-kk-CUT hardness. The surrounding text notes that the three-candidate case is proved only for the narrower range .0234ρ.1082-.0234\leq\rho\leq.1082, while the conjecture is expected for the stated range; the notation retains the source's parameter mm.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Steven Heilman, “Three Candidate Plurality is Stablest for Correlations at most 1/10”, arXiv:2306.03312 (2023).

Additional references

2 papers in this index state this conjecture (2012–2023). The statement above is taken from the most recent of them; the others are arXiv:1211.7138.

Solutions 0

No solutions have been posted yet.