An isoperimetric inequality for the Hamming cube and some consequences.

Our basic result, an isoperimetric inequality for Hamming cube Qn, can be written: ∫hAβdμ ≥ 2μ (A)(1−μ (A)). Here μ is uniform measure on V = {0,1\}n (= V(Qn)); β = log2(3/2); and, for S ⊆ V and x ∈ V, hS(x) = {dV\S(x) if x ∈ S, 0 if x ∉ S (where dT(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 Qn is (1+o(1))2n exp 2[2n-2]. This asymptotic statement, whose proof will appear separately, was the original motivation for the present work. [ABSTRACT FROM AUTHOR]