Two-part set systems

Abstract

The two part Sperner theorem of Katona and Kleitman states that if $X$ is an $n$-element set with partition $X_1\cup X_2$, and $\cF$ is a family of subsets of $X$ such that no two sets $A, B \in \cF$ satisfy $A\subset B$ (or $B\subset A$) and $A\cap X_i=B\cap X_i$ for some $i$, then $|\cF| \le {n \choose \lfloor n/2 \rfloor}$. We consider variations of this problem by replacing the Sperner property with the intersection property and considering families that satisfiy various combinations of these properties on one or both parts $X_1$, $X_2$. Along the way, we prove the following new result which may be of independent interest: let $\cF, \cG$ be families of subsets of an $n$-element set such that $\cF$ and $\cG$ are both intersecting and cross-Sperner, meaning that if $A \in \cF$ and $B \in \cG$, then $A\not\subset B$ and $B\not\subset A$. Then $|\cF| +|\cG| < 2^{n-1}$ and there are exponentially many examples showing that this bound is tight.