= Solution
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.
Back to article page
