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

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.