= 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_2a+b\log_2b)/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)\ge2t$, so $a\log_2a+b\log_2b+2\min(a,b)\le m\log_2m$. The convention is $0\log_20=0$.
A $k$-dimensional coordinate subcube has $2^k$ vertices and $k2^{k-1}$ internal edges, attaining the bound. Therefore
$$
\boxed{f(2^k)=2^k(n-k)}.
$$
Back to article page
