An isoperimetric inequality for the hamming cube and some consequences

Our basic result, an isoperimetric inequality for Hamming cube Q_n, can be written: h^β_Adμ ≥ 2μ(A)(1 − μ(A)). Here μ is uniform measure on V = {0, 1}ⁿ (= V (Q_n)); β = log₂(3/2); and, for S ⊆ V and x ∈ V , _hS(x) = d _{0 V} \_S(x) if x ∈ S, if x ∈/ S (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ⁿ−²]. This asymptotic statement, whose proof will appear separately, was the original motivation for the present work.