Equality cases of entropy cube edge-isoperimetry

ID: equality-cases-of-entropy-cube-edge-isoperimetry

For a nonempty subset of a hypercube graph, split it into sections of sizes . The proof of the entropy edge bound uses , . Strict concavity makes equality possible only at or . In the first case one section is empty; in the second the sections coincide, since all possible crossing edges must be present. Induction forces a coordinate subcube. Conversely every coordinate subcube has the displayed edge count. At size these are exactly the two halves determined by fixing one coordinate.

New to topics? Read the docs here!