Use the four families from the hint. Put $N=2^n$, $u=|\mathcal U_1|/N$, and $v=|\mathcal V_1|/N$. The families $\mathcal U_1,\mathcal V_1$ are up-sets, while their complements $\mathcal U_2,\mathcal V_2$ are down-sets. Applying the <Harris-Kleitman inequality> to the up-sets, and equivalently to the down-sets after taking complements of the ground set, gives
$$
|\mathcal U_1\cap\mathcal V_1|\geq Nuv,
\qquad
|\mathcal U_2\cap\mathcal V_2|\geq N(1-u)(1-v).
$$
The cross-incomparability assumption gives
$$
\mathcal A\subseteq\mathcal U_1\cap\mathcal V_2,
\qquad
\mathcal B\subseteq\mathcal U_2\cap\mathcal V_1.
$$
Consequently
$$
|\mathcal A|\leq Nu(1-v),
\qquad
|\mathcal B|\leq N(1-u)v.
$$
The <Cauchy-Schwarz inequality> now yields
$$
\sqrt{|\mathcal A|}+\sqrt{|\mathcal B|}
\leq\sqrt N\bigl(\sqrt{u(1-v)}+\sqrt{(1-u)v}\bigr)
\leq\sqrt N=2^{n/2}.
$$
This is the sharp two-family <Cross-Sperner inequality>.

Solution

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

 Solution

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