Abstract
We prove the following stability version of the edge isoperimetric inequality for the cube: any subset of the cube with average boundary degree within K of the minimum possible is ε-close to a union of L disjoint cubes, where L≤ L(K, ε) is independent of the dimension. This extends a stability result of Ellis, and can viewed as a dimension-free version of Friedgut's junta theorem.
Original language | English |
---|---|
Pages (from-to) | 360-375 |
Number of pages | 16 |
Journal | Journal of Combinatorial Theory, Series A |
Volume | 155 |
Early online date | 24 Nov 2017 |
DOIs | |
Publication status | Published - 1 Apr 2018 |
Keywords
- Isoperimetric inequality.
- hypercube
- Boolean analysis
- Stability