2019/09/10 by Kahn, Jeff, Park, Jinyoung · 1 citation
#05D05 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1909.04274
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) = \begincases dV ∖ S(x) amp; if x ∈ S, 0 amp; if x ∉ S \endcases (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))2nexp2[2n-2]. This asymptotic statement, whose proof will appear separately, was the original motivation for the present work.