Binary order on the discrete cube

Identify a vertex $(x_1,\dots ,x_n)$ with the integer ${\sum }_{i=1}^n{2}^{i-1}{x}_i$. Binary order is increasing order of these integers. Its initial segment of size $a$ has $F(a)={\sum }_{j=0}^{a-1}{s}_2(j)$ induced edges, where $s_2(j)$ is the Hamming weight of the binary expansion of $j$.

Fix a coordinate of the Boolean hypercube, delete it in each of the two sections, and replace each section by a binary initial segment of the same size. This preserves the total size. Mathematical induction on dimension proves that it does not decrease contained edge counts; the crossing contribution is the size of the section intersection, maximized by nested initial segments.

If both sections for every coordinate are binary initial segments, then the family itself is a binary initial segment, apart from the possible family $(\mathcal{P}([n-1])\setminus \{[n-1]\})\cup \{\{n\}\}$. Any missing vertex earlier than a present vertex must disagree with it in every coordinate; the two are therefore complementary and consecutive in binary order on the discrete cube, forcing this sole exceptional shape.

An initial segment of the binary order on the discrete cube contains the vertices whose integer encodings are $0,\dots ,m-1$. It is a down-set, so its internal edges and two-dimensional cube faces can be counted at their unique upper vertices by ${\sum }_{j<m}\mathrm{wt}(j)$ and ${\sum }_{j<m}\left(\genfrac{}{}{0ex}{}{\mathrm{wt}(j)}{2}\right)$.

For $F(a)={\sum }_{j=0}^{a-1}{s}_2(j)$ and nonnegative integers $a,b$, the displayed inequality follows by induction from $F(2r)=2F(r)+r$ and $F(2r+1)=F(r)+F(r+1)+r$. Splitting a vertex set of a hypercube graph into its two coordinate sections then proves the edge-isoperimetric theorem for binary initial segments.