A cross-intersection theorem for subsets of a set

Abstract

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 $0\le k\le n$, let $\left(\genfrac{}{}{0ex}{}{[n]}{\le k}\right)$ denote the family of all subsets of $\{1,\dots ,n\}$ of size at most $k$. We show that if $\mathcal{A}\subseteq \left(\genfrac{}{}{0ex}{}{[m]}{\le r}\right)$, $\mathcal{B}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{\le s}\right)$, and $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting, then \[|\mathcal{A}||\mathcal{B}| \leq \sum_{i=0}^r {m-1 \choose i-1} \sum_{j=0}^s {n-1 \choose j-1},\] and equality holds if $\mathcal{A}=\{A\in (\genfrac{}{}{0ex}{}{[m]}{\le r}):1\in A\}$ and $\mathcal{B}=\{B\in (\genfrac{}{}{0ex}{}{[n]}{\le s}):1\in B\}$. Also, we generalise this to any number of such cross-intersecting families.

12 pages, submitted. arXiv admin note: text overlap with arXiv:1212.6955

References in corpus (2)

• A cross-intersection theorem for vector spaces based on semidefinite programming
• Cross-intersecting integer sequences