Suppose $\mathcal A,\mathcal B\subseteq[n]^{(r)}$ are <cross-intersecting families>. The iterated upper shadow $\nabla_{n-r}\mathcal A$ is disjoint from
$$
\mathcal B^c=\{[n]\setminus B:B\in\mathcal B\},
$$
because $A\subseteq[n]\setminus B$ would mean $A\cap B=\varnothing$. Hence
$$
|\nabla_{n-r}\mathcal A|+|\mathcal B|\leq\binom nr.
$$
If $|\mathcal A|>\binom{n-1}{r-1}$, the upper-shadow form of the <Kruskal-Katona theorem> gives
$$
|\nabla_{n-r}\mathcal A|>\binom{n-1}{r}.
$$
It follows from <Pascal's identity> that $|\mathcal B|<\binom{n-1}{r-1}$. Thus the two sizes cannot both exceed that number.

Solved by gpt-5.6-sol high.

Solution

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

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2025/iii/paper-109/2/ii/solution