Plurality is Stablest conjecture for kk candidates

About 14 years old · traced to

For k≥2k\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 Inf⁡i(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 1k∑j=1kej\frac1k\sum_{j=1}^{k}e_j. For every ρ∈[−1/(m−1),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 Inf⁡i(fj)≤τ\operatorname{Inf}_{i}(f_j)\leq\tau for all ii and jj.

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

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

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

Sρf≥lim⁡n→∞Sρ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.

References

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.

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.