= Entropy proof of cube edge-isoperimetry
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_2a+b\log_2b)/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)\ge2t$, hence $a\log_2a+b\log_2b+2\min(a,b)\le m\log_2m$. Thus at most $m\log_2m/2$ internal edges are present, and the <edge boundary> is at least $m(n-\log_2m)$. Coordinate subcubes attain equality when $m$ is a power of two.
Back to article page
