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

Every positive integer $m$ has a unique binomial representationDefineThe Kruskal-Katona theorem says that every $r$-uniform family $\mathcal{A}$ of size $m$ hasand the initial segment of length $m$ in colexicographic order attains equality.

We prove the inequality by simultaneous mathematical induction on the ground-set size and on $r$. We use the elementary binomial-shadow arithmetic lemmaTo verify the lemma, greedily remove the largest term $\left(\genfrac{}{}{0ex}{}{q}{r}\right)$ from the binomial representation of $a+b$. If $a$ reaches that term first, apply the induction hypothesis to the remainders; otherwise transfer the excess to $b$. In the crossing case Pascal's identitygives exactly the two terms on the right. This induction also proves uniqueness of the greedy representation.

Choose the largest ground-set element $x$ and splitThe members of the lower shadow that avoid $x$ form $\partial {\mathcal{A}}_0\cup {\mathcal{A}}_1$, while those containing $x$ are the sets $B\cup \{x\}$ with $B\in \partial {\mathcal{A}}_1$. Hence, writing $a=|{\mathcal{A}}_0|$ and $b=|{\mathcal{A}}_1|$,This completes the induction.

Finally, the initial colex segment first contains all $r$-subsets of $[a_r]$, followed recursively by sets containing $a_r+1$ whose remaining elements form the appropriate initial segment at level $r-1$. Its shadow has the same recursive decomposition, and therefore has exactly $f_r(m)$ members. This proves sharpness.

Solved by gpt-5.6-sol high.

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.

The assertion is false. Take $n=6$, $r=3$, andThere are $1+3\cdot 3=10$ members. Its lower shadow consists of the three pairs inside $\{1,2,3\}$ and the nine pairs having one point there and one in $\{4,5,6\}$, so $|\partial \mathcal{A}|=12$. Its upper shadow consists of the twelve four-sets containing at least two points of $\{1,2,3\}$, so $|\nabla \mathcal{A}|=12$. The sum is $24$.

The initial lex segment of length ten is the star of all triples containing $1$; its lower and upper shadows have sizes $15$ and $10$. The initial colex segment consists of all triples in $[5]$; its lower and upper shadows have sizes $10$ and $15$. Both sums are $25$, so neither canonical segment minimizes the sum.

Solved by gpt-5.6-sol high.