Edge-isoperimetric inequality in the discrete cube

For $A\subseteq \{0,1{\}}^n$,

Equivalently, $A$ spans at most $\frac{1}{2}|A|{\log }_2|A|$ cube edges. Induction on the dimension and concavity of binary entropy prove the inequality.

For a vertex set of size $m$ in a hypercube graph, split one coordinate into sections of sizes $a,b$. Induction bounds the internal edges within the sections by $(a{\log }_{2}a+b{\log }_{2}b)/2$; at most $\min (a,b)$ edges cross between them. Put $t=\min (a,b)/(a+b)$. The chord bound for the binary entropy function gives $H_2(t)\ge 2t$, hence $a{\log }_{2}a+b{\log }_{2}b+2\min (a,b)\le m{\log }_{2}m$. Thus at most $m{\log }_{2}m/2$ internal edges are present, and the edge boundary is at least $m(n-{\log }_{2}m)$. Coordinate subcubes attain equality when $m$ is a power of two.

For a nonempty subset of a hypercube graph, split it into sections of sizes $a,b$. The proof of the entropy edge bound uses $H_2(t)\ge 2t$, $t=\min (a,b)/(a+b)$. Strict concavity makes equality possible only at $t=0$ or $t=1/2$. In the first case one section is empty; in the second the sections coincide, since all possible crossing edges must be present. Induction forces a coordinate subcube. Conversely every coordinate subcube has the displayed edge count. At size $2^{n-1}$ these are exactly the two halves determined by fixing one coordinate.

Among subsets of the $n$-dimensional hypercube graph with $a$ vertices, initial segments of the binary order on the discrete cube minimize the edge boundary. Its exact minimum is $na-2{\sum }_{j=0}^{a-1}{s}_2(j)$. This strengthens the entropy lower bound on the same boundary.

Among families of a given size in the Boolean hypercube, a binary initial segment maximizes the number of contained two-dimensional cube faces. Under section compression in binary order, faces crossing the selected coordinate correspond to internal edges in the intersection of its two sections. The edge extremal theorem and mathematical induction control that contribution and the faces within the sections.

The binary entropy function isIt is concave on $[0,1]$ and satisfies $H_2(x)\ge 2x$ for $0\le x\le 1/2$ by comparison with the chord from $(0,0)$ to $(1/2,1)$.