An isoperimetric inequality for the Hamming cube and some consequences

Our basic result, an isoperimetric inequality for Hamming cube $Q_n$, can be written: $$\int h_A^{\beta }d\mu \ge 2\mu (A)(1-\mu (A))\mathrm{.}$$ Here $\mu$ is uniform measure on $V=\{0,1{\}}^n$ ($=V(Q_n)$); $\beta ={\log }_2(3\mathrm{/}2)$; and, for $S\subseteq V$ and $x\in V$, $$h_S(x)=\{\begin{array}{lll}{d}_{V\setminus S}(x)& ifx\in S,0& ifx\mathrm{\notin }S\end{array}$$ (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 $\mathrm{\mid }V\mathrm{\mid }\mathrm{/}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.