2026-07 Hybercube isoperimetric inequality

Let
\[
Q_n=\{0,1\}^n
\]
be the \(n\)-dimensional discrete cube, viewed as a graph in which two vertices are adjacent if they differ in exactly one coordinate.

For a subset \(A\subseteq Q_n\), let \(\partial_e A\) denote the set of edges with one endpoint in \(A\) and the other in \(Q_n\setminus A\).

Prove that for every \(A\subseteq Q_n\),
\[
|\partial_e A|\ge |A|\bigl(n-\log_2|A|\bigr).
\]

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.