Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 11 / 1 / i / Solution

Let $e(A)$ count internal edges of the hypercube graph. Since each vertex has degree $n$, its edge boundary is $b_e(A)=n|A|-2e(A)$. The edge-isoperimetric inequality in the discrete cube gives $e(A)\le |A|{\log }_2|A|/2$, hence $b_e(A)\ge |A|(n-{\log }_2|A|)$.

For completeness, the entropy proof of cube edge-isoperimetry splits the final coordinate into sections of sizes $a,b$. Their internal edges contribute at most $(a{\log }_{2}a+b{\log }_{2}b)/2$ by induction, and their crossing edges at most $\min (a,b)$. For $m=a+b$ and $t=\min (a,b)/m$, the binary entropy function satisfies $H_2(t)\ge 2t$, so $a{\log }_{2}a+b{\log }_{2}b+2\min (a,b)\le m{\log }_{2}m$. The convention is $0{\log }_{2}0=0$.

A $k$-dimensional coordinate subcube has $2^k$ vertices and $k{2}^{k-1}$ internal edges, attaining the bound. Therefore