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

We prove the Harris-Kleitman inequality by induction on $n$. For up-sets $\mathcal{A},\mathcal{B}\subseteq \mathcal{P}([n])$, let ${\mathcal{A}}_0,{\mathcal{A}}_1$ be their sections according as $n$ is absent or present, and write $a_i=|{\mathcal{A}}_i|$; define $b_i$ and $c_i=|{\mathcal{A}}_i\cap {\mathcal{B}}_i|$ similarly. Monotonicity gives $a_0\le a_1$ and $b_0\le b_1$. The induction hypothesis on $[n-1]$ givesIt remains only to observe thatHenceThe case $n=0$ starts the induction, so this is a proof from first principles.

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, givesThe cross-incomparability assumption givesConsequentlyThe Cauchy-Schwarz inequality now yieldsThis is the sharp two-family Cross-Sperner inequality.