Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 13 / 4 / a

Identify the vertices of the Boolean hypercube with subsets of $[n]$. Write $N(\mathcal{A})$ for the closed vertex neighbourhood and $\partial \mathcal{A}=N(\mathcal{A})\setminus \mathcal{A}$ for the external vertex boundary. The cube order used here is the simplicial order on the discrete cube: increasing size, then lexicographic order, with the smallest differing coordinate belonging to the earlier set. We prove Harper theorem by induction on $n$; subtracting the common size of the families converts a closed-neighbourhood comparison into the required boundary comparison.

First, the closed neighbourhood of a simplicial initial segment is itself an initial segment. Such a family consists of full lower levels and a lexicographic initial part of its last level. Its next-level neighbours form the upper shadow of that part. For a set in the next level, its lexicographically earliest lower-level subset is obtained by deleting its largest element. This map preserves the lexicographic order weakly. Membership in the upper shadow is equivalent to that earliest subset belonging to the original initial part, so the upper shadow is an initial part too. Empty and full families satisfy the assertion directly.

Assume the theorem in dimension $n-1$. Split $\mathcal{A}$ into two sections ${\mathcal{A}}_0,{\mathcal{A}}_1$ according to membership of coordinate $i$, deleting $i$ from the second section. Their closed-neighbourhood sections areReplace each section by a simplicial initial segment $I_0,I_1$ of the same size. Induction gives $|N(I_j)|\le |N({\mathcal{A}}_j)|$. By the preceding observation, each $N(I_j)$ is an initial segment and is nested with the other section. Consequentlyand the analogous inequality holds for the other section. Thus simplicial section compression preserves size and cannot increase the closed neighbourhood.

Repeatedly apply a nontrivial section compression. The sum of the positions of the family members in the full simplicial order strictly decreases: the order induced on either fixed-coordinate section is precisely its lower-dimensional simplicial order. This positive integer potential makes the process terminate at a family $\mathcal{B}$ fixed by every section compression.

We classify such terminal families for simplicial section compression. If an earlier vertex $x$ is absent while a later vertex $y$ is present, they cannot agree at any coordinate, since the corresponding section is an initial segment. Hence $y=x^c$. Every other vertex earlier than $y$ is present, and every other vertex later than $x$ is absent, since any further inverted pair would also have to be complementary. There can therefore be no vertex strictly between $x$ and $y$. Thus $\mathcal{B}$ either is an initial segment or is an initial segment with its last vertex replaced by the next, complementary vertex.

The complementary consecutive pairs are explicit. If $n=2r+1$, the ranks must be $r$ and $r+1$, and consecutive order positions forceThe corresponding initial segment $I$ contains all sets of size at most $r$, and $\mathcal{B}=I-\{x\}+\{y\}$. Its closed neighbourhood contains all sets of size at most $r+1$: for $r\ge 1$, deletion of just one $r$-set cannot remove all the $r$-subsets of any $(r+1)$-set, and $x$ remains adjacent to one of its $(r-1)$-subsets. In addition, the $r$ supersets of $y$ of size $r+2$ enter the neighbourhood. Thus $|N(\mathcal{B})|=|N(I)|+r$; the $n=1$ case gives equality directly.

If $n=2r$, the two vertices have rank $r$. Complementation reverses the lexicographic order within that rank, so consecutive complements occupy its middle two positions. These areNow $I$ contains all sets of size less than $r$ and all $r$-sets containing coordinate one. Its closed neighbourhood contains all sets of size at most $r$ and all $(r+1)$-sets containing one. For $r\ge 2$, each such $(r+1)$-set has at least two $r$-subsets containing one, so exchanging $x$ for $y$ loses none of these neighbours. It adds the $r-1$ supersets of $y$ of size $r+1$ that avoid one. Hence $|N(\mathcal{B})|=|N(I)|+r-1$. For $n=2$ the two neighbourhoods are both the entire cube.

In both exceptional cases the initial segment has no larger neighbourhood. The induction starts with the one-vertex zero-dimensional cube, and the compression argument now proves