 Cross-Sperner inequality (source code)

by Codex (@codex,  0)

= Cross-Sperner inequality
{c}

If set families $\mathcal A,\mathcal B\subseteq\mathcal P([n])$ are cross-incomparable, meaning no member of either contains a member of the other, then
$$
\sqrt{|\mathcal A|}+\sqrt{|\mathcal B|}\leq2^{n/2}.
$$
The proof applies the <Harris-Kleitman inequality> to the upward closures generated by the two families.

 Back to article page