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

Abstract

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

arXiv comment14 pages