Vertex-isoperimetric inequality in the discrete cube ($|N(\mathcal{A})|\ge |N(I_{|\mathcal{A}|})|$)

For the Boolean hypercube, the initial segment of the simplicial order on the discrete cube minimizes the size of the closed vertex neighbourhood among families of a given size. Equivalently, it minimizes the external vertex boundary. This is a vertex assertion, distinct from the edge-isoperimetric inequality in the discrete cube.

For $n\ge 1$, a family of $2^{n-1}$ vertices in the Boolean hypercube has these minimum and maximum external vertex boundary sizes. The Harper theorem gives the minimum: in odd dimension take the lower half of the levels, and in even dimension add the middle-level sets containing coordinate one to all lower levels. The family of even Hamming weight attains the maximum, since every remaining vertex has an adjacent even-weight vertex.

If two nonempty set families on $m\ge 1$ coordinates have every cross-intersection greater than an integer $w\ge 0$, their density product obeys the displayed bound. Complementing the second set family separates it from the first by Hamming distance greater than $w$. Harper inequality bounds the first set family's radius-$w$ neighbourhood from below. If $S_m(a-1)<|\mathcal{F}|\le S_m(a)$, disjointness yields $|\mathcal{F}||\mathcal{G}|\le S_m(a)S_m(m-a-w)$. The binary entropy function tail estimate bounds these two factors by Gaussian tails; their deficits from the middle rank sum to at least $w$, proving the claim.

Equality in Harper theorem need not make a down-set a cube-automorphic image of a simplicial initial segment. In $Q_4$, take all sets of size at most one and the four two-element sets forming a four-cycle. This family has size nine and closed graph neighbourhood size fifteen, just like the size-nine simplicial order on the discrete cube initial segment. The induced degree of a vertex distributions differ, so they cannot be related by a graph automorphism.

Split a set family in the hypercube graph according to whether coordinate $i$ is present, and delete that coordinate from the present section. Replace both sections by initial segments of the simplicial order on the discrete cube with the same respective sizes. Induction and nesting of initial-segment closed graph neighbourhoods show that this operation cannot enlarge the original closed graph neighbourhood. Repeated nontrivial compressions terminate because the sum of simplicial positions strictly decreases.

A family fixed by every simplicial section compression is either an initial segment of the simplicial order on the discrete cube or that segment with its last vertex exchanged for the next vertex, where the exchanged vertices are complementary. Indeed, an earlier absent vertex and a later present vertex must differ in every coordinate, and cannot have another vertex between them. Complementary consecutive vertices occur only across the two central ranks in odd dimension, or at the transition from middle-rank sets containing coordinate one to those avoiding it in even dimension. Direct closed graph neighbourhood comparison resolves these exceptions in the proof of Harper theorem.

Adjoin all lower levels to a uniform set family before applying Harper theorem. Its remaining neighbourhood contribution is the upper shadow, so lexicographic initial segments minimize upper shadows. Complementation and reversal of coordinates turn this into colexicographic order minimizing the lower shadow, giving the Kruskal-Katona theorem.