论文标题
对于小相关性，三个候选多数是最稳定的
Three Candidate Plurality is Stablest for Small Correlations
论文作者
论文摘要
使用变量的计算，我们证明了以下噪声稳定分区的结构定理：$ n $维的欧几里得空间的分区中的分区中，$ m $ diss of $ m $ dissect of固定的高斯量，最大化其噪声稳定性必须为$（M-1）$ - 尺寸 - 如果$ m-dimensiation，如果$ m-1 \ m-1 \ m-1 \ leq N $。特别是，对于满足$ n \ geq m-1 $的所有$ n $，固定高斯量的$ \ mathbb {r}^{n} $的$ m $设置的分区的最大噪声稳定性都是恒定的。从这个结果，我们获得： （i）多数的证明是$ 3 $候选选举的最稳定的猜想，对于所有相关参数，$ρ$满足$ 0 <ρ<ρ_{0} $，其中$ρ_{0}> 0 $是固定的常数（不取决于$ n $ n $ n $ n $ n $ n时，每个候选人都有一个平等的机会。 （ii）Borell不平等的变异证明（对应于$ M = 2 $的情况）。 定理的结构回答了De-Mossel-neeman和Ghazi-Kamath-Raghavendra的问题。项目（i）是任何复数情况的第一个证明是固定$ρ$的khot-kindler-mossel-o'donnell（2005）的最稳定的猜想，而最近解决了案例$ρ\ to1^{ - } $。项目（i）也是假设独特的游戏猜想，这也是Frieze-Jerrum半决赛计划的最佳证据。如果没有假设每个候选人在（i）中都有相等的胜利机会，则已知多数是最稳定的猜想是错误的。
Using the calculus of variations, we prove the following structure theorem for noise stable partitions: a partition of $n$-dimensional Euclidean space into $m$ disjoint sets of fixed Gaussian volumes that maximize their noise stability must be $(m-1)$-dimensional, if $m-1\leq n$. In particular, the maximum noise stability of a partition of $m$ sets in $\mathbb{R}^{n}$ of fixed Gaussian volumes is constant for all $n$ satisfying $n\geq m-1$. From this result, we obtain: (i) A proof of the Plurality is Stablest Conjecture for $3$ candidate elections, for all correlation parameters $ρ$ satisfying $0<ρ<ρ_{0}$, where $ρ_{0}>0$ is a fixed constant (that does not depend on the dimension $n$), when each candidate has an equal chance of winning. (ii) A variational proof of Borell's Inequality (corresponding to the case $m=2$). The structure theorem answers a question of De-Mossel-Neeman and of Ghazi-Kamath-Raghavendra. Item (i) is the first proof of any case of the Plurality is Stablest Conjecture of Khot-Kindler-Mossel-O'Donnell (2005) for fixed $ρ$, with the case $ρ\to1^{-}$ being solved recently. Item (i) is also the first evidence for the optimality of the Frieze-Jerrum semidefinite program for solving MAX-3-CUT, assuming the Unique Games Conjecture. Without the assumption that each candidate has an equal chance of winning in (i), the Plurality is Stablest Conjecture is known to be false.
