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^\beta d\mu \ge 2 \mu (A)(1-\mu (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) &\text { if } x \in S, \\ 0 &\text { 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.

Locations

• Proceedings of the American Mathematical Society - View
• arXiv (Cornell University) - View - PDF