Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 11 / 1

Let $e(A)$ count internal edges of the hypercube graph. Since each vertex has degree $n$, its edge boundary is $b_e(A)=n|A|-2e(A)$. The edge-isoperimetric inequality in the discrete cube gives $e(A)\le |A|{\log }_2|A|/2$, hence $b_e(A)\ge |A|(n-{\log }_2|A|)$.

For completeness, the entropy proof of cube edge-isoperimetry splits the final coordinate into sections of sizes $a,b$. Their internal edges contribute at most $(a{\log }_{2}a+b{\log }_{2}b)/2$ by induction, and their crossing edges at most $\min (a,b)$. For $m=a+b$ and $t=\min (a,b)/m$, the binary entropy function satisfies $H_2(t)\ge 2t$, so $a{\log }_{2}a+b{\log }_{2}b+2\min (a,b)\le m{\log }_{2}m$. The convention is $0{\log }_{2}0=0$.

A $k$-dimensional coordinate subcube has $2^k$ vertices and $k{2}^{k-1}$ internal edges, attaining the bound. Therefore

A down-set in the Boolean lattice is a family closed under taking subsets. Restricting the minimization to down-sets cannot decrease the minimum from the edge-isoperimetric inequality in the discrete cube.

The coordinate subcube consisting of all subsets of a fixed $k$-element set is itself a down-set and attains that minimum. Thus

Identify cube vertices with subsets of $[n]$. In a down-set $D$, every $A\in D$ has all its $|A|$ immediate lower neighbors in $D$. Counting each internal edge by its upper endpoint gives the edge boundary of a down-set in a cubeTo maximize it, minimize the sum of set sizes. Among all families of $m$ sets, the minimum is obtained by taking the smallest ranks first. This choice is a down-set: take every set of size below $r$, followed by any required selection of $r$-sets.

Write $M_j={\sum }_{i=0}^j\left(\genfrac{}{}{0ex}{}{n}{i}\right)$, with $M_{-1}=0$, and choose $r$ such that $M_{r-1}\le m\le M_r$. The largest edge boundary of a down-set is thereforeEquivalently, it is ${\sum }_{j<r}(n-2j)\left(\genfrac{}{}{0ex}{}{n}{j}\right)+(n-2r)(m-M_{r-1})$. This includes $m=0$ and $m=2^n$, with boundary zero. If $m$ is exactly a complete-level size, either adjacent choice of $r$ gives the same value.