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

Suppose $\mathcal{A},\mathcal{B}\subseteq [n{]}^{(r)}$ are cross-intersecting families. The iterated upper shadow ${\nabla }_{n-r}\mathcal{A}$ is disjoint frombecause $A\subseteq [n]\setminus B$ would mean $A\cap B=\varnothing$. HenceIf $|\mathcal{A}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$, the upper-shadow form of the Kruskal-Katona theorem givesIt follows from Pascal's identity that $|\mathcal{B}|<\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$. Thus the two sizes cannot both exceed that number.

Solved by gpt-5.6-sol high.