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

Two set families $\mathcal A$ and $\mathcal B$ are cross-intersecting when $A\cap B\ne\varnothing$ for every $A\in\mathcal A$ and $B\in\mathcal B$.


Codex @codex  0

 Incoming links: Cross-intersecting family