Past exam of the mathematics course of the University of Cambridge / 2005 / iii / Paper 10 / 1 / Solution

Identify the discrete cube $Q_n$ with the subsets of $[n]$, with hypercube graph adjacency given by changing one element. Write $N[A]$ for the closed graph neighbourhood and $\partial A=N[A]\setminus A$ for the external vertex boundary. The simplicial order on the discrete cube first orders by set size and then by lexicographic order, with the smallest differing coordinate belonging to the earlier set.

Harper theorem states that, for every set family $A\subseteq Q_n$,Here is the simplicial section compression proof. Induct on $n$, the one-dimensional case being immediate. Split $A$ by a coordinate into sections $A_0,A_1\subseteq Q_{n-1}$. Its neighbourhood sections areReplace $A_0,A_1$ by equally large simplicial initial segments $I_0,I_1$. By induction $|N[I_j]|\le |N[A_j]|$. Also the neighbourhood of a simplicial initial segment is itself a simplicial initial segment: at its last occupied level the extra vertices form the upper shadow of a lexicographic initial segment, again lexicographically initial. Consequently the compressed unions have sizes $\max \{|N[I_0]|,|I_1|\}$ and $\max \{|N[I_1]|,|I_0|\}$, no larger than the original unions. The compression preserves $|A|$ and cannot increase $|N[A]|$.

Repeat in every coordinate until all sections are initial. Every nontrivial compression strictly decreases the sum of the global simplicial positions, so the process terminates. To describe the terminal families for simplicial section compression, suppose an earlier absent vertex $S$ precedes a later present vertex $T$. They cannot share a coordinate value: otherwise they lie in the same compressed section, contradicting its initiality. Thus $T=[n]\setminus S$. No vertex can lie strictly between them in the order, since it would make another absent/present pair that is not complementary. Hence the terminal family is either $C(|A|)$ or that segment with its last vertex $S$ exchanged for its immediate complementary successor $T$.

For odd $n=2m+1$, that exceptional exchange crosses the middle levels: $S=\{m+2,\dots ,2m+1\}$ and $T=\{1,\dots ,m+1\}$. For $m\ge 1$, all sets of size at most $m+1$ remain in the neighbourhood after the exchange, since an $(m+1)$-set has at least two lower neighbours and only one was removed. The new $T$ can only add vertices of size $m+2$.

For even $n=2m$, the only consecutive complementary pair in one level is $S=\{1,m+2,\dots ,2m\}$ and $T=\{2,\dots ,m+1\}$. The original segment contains all sets below size $m$ and all $m$-sets containing 1. For $m\ge 2$, its neighbourhood contains all sets of size at most $m$ and all $(m+1)$-sets containing 1; every such upper set still has an included lower neighbour after the single removal. The new $T$ can only add further neighbours. The cases $n=1,2$ follow directly, with the exceptional families related to the initial ones by a graph automorphism. Thus neither exception improves the neighbourhood, completing the induction.

For the half-cube vertex-boundary extrema, if $n=2m+1$, the initial half cube is all sets of size at most $m$; its boundary is the next level, of size $\left(\genfrac{}{}{0ex}{}{2m+1}{m+1}\right)$. If $n=2m$, it contains all levels below $m$ and the $m$-sets containing 1. The boundary consists of the $m$-sets avoiding 1 and the $(m+1)$-sets containing 1, giving $2\left(\genfrac{}{}{0ex}{}{2m-1}{m}\right)=\left(\genfrac{}{}{0ex}{}{2m}{m}\right)$.

No boundary can exceed the $2^{n-1}$ vertices outside a half cube. Taking all vertices of even Hamming weight attains that bound, because every odd-weight vertex is adjacent to one of them. Therefore, for $n\ge 1$,