论文标题
边缘 - 术的不平等和球噪声稳定性：线性编程和概率方法
Edge-Isoperimetric Inequalities and Ball-Noise Stability: Linear Programming and Probabilistic Approaches
论文作者
论文摘要
令$ q_ {n}^{r} $为带顶点的图形$ \ { - 1,1 \}^{n} $，如果它们的锤距最大为$ r $，则将两个顶点连接在一起。 $ q_ {n}^{r} $的边缘 - 等法问题是：对于每个$（n，r，m）$，使$ 1 \ le r \ le r \ le \ le n $和$ 1 \ le m \ le2^{n} $，确定$ q_} $ q_} $ q_} $ q_} $ q _} $ q _} $ qudtices的最小边缘式尺寸的边缘大小。在本文中，我们采用两种不同的方法来证明此问题的界限。第一种方法是一种线性编程方法，第二种方法是一种概率方法。我们通过第一种方法得出的界限将$ m = 2^{n-1} $概括为1989年Kahn，Kalai和Linial衍生的限制。此外，我们的界限也很紧，对于$ M = 2^{n-2} $和$ r \ le \ le \ le \ le \ frac {n} {n} {2} {2}} -1 $ $。第二种方法得出的我们的界限是根据\ emph {噪声稳定性}表示的，并且在$ r = 2 \ lfloor \ lfloor \ frac {βn} {2} {2} {2} {2} {2} {2} \ rfloor+1 $ and $ m = \ lfloor $ $ = \ alfloor $ pha时$α，β\ in（0,1）$，当$ r = 2 \ lfloor \ frac {βn} {2} {2} \ rfloor $和$ m = \ lfloor \ lfloor \ alpha2^{n} {n} \ rfloor $时。实际上，边缘相容性问题等同于球噪声稳定性问题，该问题是传统（I.I.D.-）噪声稳定性问题的变体。我们的结果可以解释为噪声稳定性问题的范围。
Let $Q_{n}^{r}$ be the graph with vertex set $\{-1,1\}^{n}$ in which two vertices are joined if their Hamming distance is at most $r$. The edge-isoperimetric problem for $Q_{n}^{r}$ is that: For every $(n,r,M)$ such that $1\le r\le n$ and $1\le M\le2^{n}$, determine the minimum edge-boundary size of a subset of vertices of $Q_{n}^{r}$ with a given size $M$. In this paper, we apply two different approaches to prove bounds for this problem. The first approach is a linear programming approach and the second is a probabilistic approach. Our bound derived by the first approach generalizes the tight bound for $M=2^{n-1}$ derived by Kahn, Kalai, and Linial in 1989. Moreover, our bound is also tight for $M=2^{n-2}$ and $r\le\frac{n}{2}-1$. Our bounds derived by the second approach are expressed in terms of the \emph{noise stability}, and they are shown to be asymptotically tight as $n\to\infty$ when $r=2\lfloor\frac{βn}{2}\rfloor+1$ and $M=\lfloor\alpha2^{n}\rfloor$ for fixed $α,β\in(0,1)$, and is tight up to a factor $2$ when $r=2\lfloor\frac{βn}{2}\rfloor$ and $M=\lfloor\alpha2^{n}\rfloor$. In fact, the edge-isoperimetric problem is equivalent to a ball-noise stability problem which is a variant of the traditional (i.i.d.-) noise stability problem. Our results can be interpreted as bounds for the ball-noise stability problem.
