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