The maximum sum of sizes of cross-intersecting families of subsets of a set

Abstract

A set of sets is called a family. Two families $\mathcal{A}$ and $\mathcal{B}$ of sets are said to be cross-intersecting if each member of $\mathcal{A}$ intersects each member of $\mathcal{B}$. For any two integers $n$ and $k$ with $1\le k\le n$, let $\left(\genfrac{}{}{0ex}{}{[n]}{\le k}\right)$ denote the family of subsets of $[n]=\{1,\dots ,n\}$ that have at most $k$ elements. We show that if $\mathcal{A}$ is a non-empty subfamily of $\left(\genfrac{}{}{0ex}{}{[n]}{\le r}\right)$, $\mathcal{B}$ is a non-empty subfamily of $\left(\genfrac{}{}{0ex}{}{[n]}{\le s}\right)$, $r\le s$, and $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting, then \[|\mathcal{A}| + |\mathcal{B}| \leq 1 + \sum_{i=1}^s \left({n \choose i} - {n-r \choose i} \right),\] and equality holds if $\mathcal{A}=\{[r]\}$ and $\mathcal{B}$ is the family of sets in $\left(\genfrac{}{}{0ex}{}{[n]}{\le s}\right)$ that intersect $[r]$.

7 pages, a typo in the abstract and in Theorem 1 has been corrected. arXiv admin note: text overlap with arXiv:1402.3969