An isoperimetric inequality for the Hamming cube and some consequences

Abstract

Our basic result, an isoperimetric inequality for Hamming cube $Q_n$, can be written: \[ \int h_A^βdμ\ge 2 μ(A)(1-μ(A)). \] Here $\mu$ is uniform measure on $V=\{0,1{\}}^n$ ($=V(Q_n)$); $\beta ={\log }_2(3/2)$; and, for $S\subseteq V$ and $x\in V$, \[ h_S(x) = \begin{cases} d_{V \setminus S}(x) &\mbox{ if } x \in S, 0 &\mbox{ if } x \notin S \end{cases} \] (where $d_T(x)$ is the number of neighbors of $x$ in $T$). This implies inequalities involving mixtures of edge and vertex boundaries, with related stability results, and suggests some more general possibilities. One application, a stability result for the set of edges connecting two disjoint subsets of $V$ of size roughly $|V|/2$, is a key step in showing that the number of maximal independent sets in $Q_n$ is $(1+o(1))2n{\exp }_2[2^{n-2}]$. This asymptotic statement, whose proof will appear separately, was the original motivation for the present work.

arXiv comment12 pages, 1 figure (v2: reference updated)