Analogues of Katona's and Milner's Theorems for two families

Peter Frankl, Willie Wong H. W

Published 2020-06-22Version 1

Let $n>s>0$ be integers, $X$ an $n$-element set and $\mathscr{A}, \mathscr{B}\subset 2^X$ two families. If $|A\cup B|\le s$ for all $A\in\mathscr{A}, B\in \mathscr{B}$, then $\mathscr{A}$ and $\mathscr{B}$ are called cross $s$-union. Assuming that neither $\mathscr{A}$ nor $\mathscr{B}$ is empty, we prove several best possible bounds. In particular, we show that $|\mathscr{A}|+|\mathscr{B}|\le 1+\sum\limits_{0\le i\le s}{{n}\choose{i}}$. Supposing $n\ge 2s$ and $\mathscr{A},\mathscr{B}$ are antichains, we show that $|\mathscr{A}|+|\mathscr{B}|\le {{n}\choose{1}}+{{n}\choose{s-1}}$ unless $\mathscr{A}=\{\emptyset\}$ or $\mathscr{B}=\{\emptyset\}$. An analogous result for three families is established as well.