Entropy proof of cube edge-isoperimetry

ID: entropy-proof-of-cube-edge-isoperimetry

For a vertex set of size in a hypercube graph, split one coordinate into sections of sizes . Induction bounds the internal edges within the sections by ; at most edges cross between them. Put . The chord bound for the binary entropy function gives , hence . Thus at most internal edges are present, and the edge boundary is at least . Coordinate subcubes attain equality when is a power of two.

New to topics? Read the docs here!