Edge-Isoperimetric Inequalities and Ball-Noise Stability: Linear Programming and Probabilistic Approaches
share
Let Q_n^r be the r-power of the hypercube {-1,1}^n. The discrete edge-isoperimetric problem for Q_n^r is that: For every (n,r,M) such that 1< r< n and 1< M<2^n, determine the minimum 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. Our first approach is a linear programming approach and the second is a probabilistic approach. Our bound derived by using the first approach generalizes the sharp bound for M=2^n-1 derived by Kahn, Kalai, and Linial in 1989. Moreover, our bound is also sharp for M=2^n-2 and r<n-1/2. Our bound derived by using the second approach is asymptotically sharp as n→∞ when r=2β n/2 +1 and M=α2^n for fixed α,β∈(0,1), and sharp up to a constant factor when r=2β n/2 and M=α2^n. Furthermore, the discrete 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 imply bounds on the ball-noise stability problem.
READ FULL TEXT