Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 109 / 1 / ii / Solution

Let $c(A)=[n]\setminus A$ and reverse the order of the ground set by $j\mapsto n+1-j$. The resulting bijection sends lexicographic order on $[n{]}^{(r)}$ to colexicographic order on $[n{]}^{(n-r)}$. It also sends the iterated upper shadow of an $r$-uniform family at level $r+1$ to the lower shadow of the corresponding $(n-r)$-uniform family, up to the same harmless reversal of the ground set.

The Kruskal-Katona theorem says that this lower shadow is smallest for an initial colex segment. Undoing the complement and reversal therefore says that the upper shadow of a family of fixed size in $[n{]}^{(r)}$ is smallest for the initial lex segment.

Solved by gpt-5.6-sol high.