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!