Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 11 / 3

Use the external external vertex boundary conventionEquivalently, its closed graph neighbourhood is $N[\mathcal{A}]=\mathcal{A}\cup B(\mathcal{A})$. Some boundary conventions use this closed graph neighbourhood itself; because the compared set families have equal size, either convention gives the same inequality.

Order the Boolean lattice first by increasing size, and within a size by lexicographic order, with the smallest differing coordinate in the earlier set. If $I$ is the initial segment in this simplicial order on the discrete cube with $|I|=|\mathcal{A}|$, Harper inequality isIn particular, writing $S_n(t)={\sum }_{j=0}^t\left(\genfrac{}{}{0ex}{}{n}{j}\right)$, if $|\mathcal{A}|\ge S_n(t)$ then $|N[\mathcal{A}]|\ge S_n(t+1)$.

Here is the full simplicial section compression proof. The cases $n=0,1$ are immediate. A simplicial initial segment has an initial-segment closed graph neighbourhood: it contains every smaller level, and its remaining upper level is the upper shadow of a lexicographic initial segment. That upper shadow is lexicographic initial because a set has a face in the segment exactly when its earliest face does, and earliest faces preserve lexicographic order.

Assume the result in dimension $n-1$. For a coordinate $i$, delete it from the present section and write the two sections as ${\mathcal{A}}_0,{\mathcal{A}}_1$. Their neighbourhood sections are exactlyReplace both sections by equally large simplicial initial segments $I_0,I_1$. The mathematical induction hypothesis controls each internal neighbourhood. Both sets in each new union are initial segments, so that union has size equal to the larger of their sizes. The corresponding old union has at least that size. Therefore this simplicial section compression does not enlarge $N[\mathcal{A}]$.

Repeatedly compress any noninitial section. Every change strictly reduces the sum of the global simplicial positions of the set family members, so the process terminates at a set family $\mathcal{C}$ compressed in every section. Suppose an earlier vertex $X$ is missing while a later vertex $Y$ is present. If they agree in any coordinate, they contradict compression of that coordinate's section. Thus $Y=[n]\setminus X$. They must also be consecutive in simplicial order: an intermediate vertex, whether present or absent, would create another inversion and would have to equal one of these two complementary vertices. No other inversion is possible for the same reason. Hence $\mathcal{C}$ is either the required initial segment or that segment with its last vertex $X$ exchanged for the next vertex $Y$, with $X,Y$ complementary.

For completeness, these terminal families for simplicial section compression can be checked explicitly. If $n=2k+1$, the exceptional consecutive vertices are the last $k$-set $X=\{k+2,\dots ,2k+1\}$ and first $(k+1)$-set $Y=\{1,\dots ,k+1\}$. For $k\ge 1$, the initial segment is all levels through $k$. After the exchange every vertex of size at most $k+1$ is still in its closed graph neighbourhood: a $(k+1)$-set has at least two $k$-faces, so deleting the one face $X$ cannot remove it, and $X$ itself neighbours a retained smaller set. Thus the new neighbourhood contains the old one. For $k=0$, the two single-vertex set families have the same neighbourhood.

If $n=2k$, the exceptional pair is $X=\{1,k+2,\dots ,2k\}$ and $Y=\{2,\dots ,k+1\}$. The initial segment consists of every level below $k$ and all $k$-sets containing coordinate one. Its closed graph neighbourhood consists of every level through $k$ and the $(k+1)$-sets containing coordinate one. For $k\ge 2$, each of the latter has $k\ge 2$ faces containing coordinate one, so deleting $X$ removes no such neighbour. Every lower level remains covered. For $k=1$, the added vertex $Y$ itself keeps the sole two-element neighbour covered. Again the exchange does not decrease the neighbourhood. These are the only complementary consecutive pairs, as is seen by checking the central ranks and the lexicographic transition between middle-rank sets containing and avoiding coordinate one.

We have reached a set family whose neighbourhood is at least the initial segment's, without increasing the original neighbourhood. This proves Harper inequality by mathematical induction, including the exceptional compressed set families often omitted from the argument.

For the final request, the usual two-coordinate shift does not increase the boundary of a uniform set family. To see this carefully, let $i\ne j$ and let $C_{ij}$ move a set containing $j$ but not $i$ to its partner with $j$ replaced by $i$, only if that partner is absent. For any uniform set family $\mathcal{F}$,Here is the local witness check for the lower shadow inclusion. A shadow member containing neither or both of $i,j$ has an old witness after possibly exchanging $i,j$ in that witness. For a paired shadow vertex containing $i$ only, either its old version or its $j$-partner has an old witness, which suffices for its membership in the shifted shadow. For a vertex containing $j$ only that survives in the new shadow, its new witness either contains both coordinates, supplying both old shadow partners directly, or is an unshifted $j$-only witness whose $i$-partner was already present. In either event both old shadow partners existed, which is exactly the condition for the $j$-vertex to survive the shadow shift. This exhausts the coordinate patterns.

Taking complements converts an upper shadow into a lower shadow and converts $C_{ij}$ into $C_{ji}$, proving the second inclusion. Each shift preserves cardinality on the shadow level. The external boundary of an $r$-uniform set family is the disjoint union of its lower and upper shadows, soThe endpoint levels $r=0,n$ have an empty shadow on one side and obey the same conclusion.