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

On the structure of subsets of the discrete cube with small edge boundary, Discrete Analysis 2018:9, 29 pp.

An isoperimetric inequality is a statement that tells us how small the boundary of a set can be given the size of the set, for suitable notions of “size” and “boundary”. For example, one formulation of the classical isoperimetric inequality in $\mathbb R^n$ is as follows. Given a subset $X$ of $\mathbb R^n$, define the $\epsilon$-expansion of $X$ to be the open set $X_\epsilon=\{y\in\mathbb R^n: d(y,X)<\epsilon\}$. If in addition $X$ is measurable, define the size of its boundary to be $\lim\inf_{\epsilon\to 0} \epsilon^{-1}\mu(X_\epsilon\setminus X)$. (If $X$ is a set with a suitably smooth topological boundary $\partial X$, then this turns out to equal the surface measure of $\partial X$.) Then amongst all sets $X$ of a given measure, the one with the smallest boundary is an $n$-dimensional ball.

Isoperimetric inequalities have been the focus of a great deal of research, partly for their intrinisic interest, but also because they have numerous applications. One particularly useful one is the edge-isoperimetric inequality in the discrete cube. This concerns subsets $X$ of the $n$-dimensional cube $\{0,1\}^n$, which we turn into a graph by joining two points $x$ and $y$ if they differ in exactly one coordinate. The size of a set $X$ is simply its cardinality, the edge-boundary of $X$ is defined to be the set of edges between $X$ and its complement, and the size of the edge-boundary is the number of such edges. If $|X|=2^d$, then it is known that the edge-boundary is minimized when $X$ is a $d$-dimensional subspace of $\mathbb F_2^n$ generated by $d$ standard basis vectors. More generally, if $|X|=m$, then the edge-boundary is minimized when $X$ is an initial segment in the lexicographical ordering, which is the ordering where we set $x<y$ if $x_i<y_i$ for the first coordinate $i$ where $x_i$ and $y_i$ differ. (This coincides with the ordering we obtain if we think of the sequences as binary representations of integers.)

For the two isoperimetric inequalities just mentioned, as well as many others, it is known that the extremal examples provided are essentially the only ones: a subset of $\mathbb R^n$ with a boundary that is as small as possible has to be an $n$-dimensional ball, and a subset of the discrete cube with edge-boundary that is as small as possible has to be an initial segment of the lexicographical ordering, up to the symmetries of the graph. Furthermore, there are stablity results: a set with a boundary that is almost as small as possible must be close to an extremal example. Such a result tells us that the isoperimetric inequalities are “robust”, in the sense that if you slightly perturb the condition on the set, then you only slightly perturb what the set has to look like.

This paper is about an extremely precise stability result for the edge isoperimetric inequality in the discrete cube. There have been a number of papers on such results (see the introduction to the paper for details), but they have been mainly for sets of size $2^d$ for some $d$, where the goal is to prove that they must be close to $d$-dimensional subcubes – that is, subspaces (or their translates) generated by $d$ standard basis vectors. This paper considers sets of arbitrary size and proves the following result. Suppose that $X$ is a subset of $\{0,1\}^n$ of size $m$. Suppose that the size of the edge-boundary of $X$ is at most $g_n(m)+l$, where $g_n(m)$ is the size of the edge-boundary of the initial segment $I_m$ of size $m$ in the lexicographical order. Then there is an automorphism $\phi$ of $\{0,1\}^n$ (meaning a bijection that takes neighbouring points to neighbouring points) such that $|X\Delta\phi(I_m)|\leq Cl$, where $C$ is an absolute constant. They give an example to show that $C$ must be at least 2, and thus that their result is best possible up to the value of the constant $C$.

Previous proofs of stability versions of the edge-isoperimetric inequality in the cube have used Fourier analysis. The proof in this paper uses purely combinatorial methods, such as induction on the dimension, and compressions. To get these methods to work, several interesting ideas are needed, including some new results about the influence of variables.