On the structure of subsets of the discrete cube with small edge boundary

Abstract

The edge isoperimetric inequality in the discrete cube specifies, for each pair of integers $m$ and $n$, the minimum size $g_n(m)$ of the edge boundary of an $m$-element subset of $\{0,1{\}}^n$; the extremal families (up to automorphisms of the discrete cube) are initial segments of the lexicographic ordering on $\{0,1{\}}^n$. We show that for any $m$-element subset $\mathcal{F}\subset \{0,1{\}}^n$ and any integer $l$, if the edge boundary of $\mathcal{F}$ has size at most $g_n(m)+l$, then there exists an extremal family $\mathcal{G}\subset \{0,1{\}}^n$ such that $|\mathcal{F}\Delta \mathcal{G}|\le Cl$, where $C$ is an absolute constant. This is best-possible, up to the value of $C$. Our result can be seen as a `stability' version of the edge isoperimetric inequality in the discrete cube, and as a discrete analogue of the seminal stability result of Fusco, Maggi and Pratelli concerning the isoperimetric inequality in Euclidean space.

arXiv comment29 pages. Reformatted for publication in Discrete Analysis