Intersecting and Cross-Intersecting Families of Labeled Sets

Abstract

A family ${\cal A}$ of sets is said to be intersecting if any two sets in ${\cal A}$ intersect. Families ${\cal A}_1, ..., {\cal A}_p$ are said to be cross-intersecting if, for any $i, j \in \{1, ..., p\}$ such that $i \neq j$, any set in ${\cal A}_i$ intersects any set in ${\cal A}_j$.

For ${\bf k} = (k_1, ..., k_n) \in {\Bbb N}^n$, $2 \leq k_1 \leq ... \leq k_n$, let ${\cal L}_{\bf{k}}$ be the family of labeled $n$-sets given by ${\cal L}_{\bf{k}} := \{\{(1,l_1), ..., (n,l_n)\} \colon l_i \in \{1, ..., k_i\}, i = 1, ..., n\}$. We point out a relationship between intersecting families and cross-intersecting families of labeled sets, and we show that, if ${\cal A}_1, ..., {\cal A}_p$ are cross-intersecting sub-families of ${\cal L}_{\bf{k}}$, then $$ \sum_{j = 1}^p |{\cal A}_j| \leq \left\{ \matrix{ k_1k_2...k_n & \hbox{if $p \leq k_1$};\cr pk_2...k_n & \hbox{if $p \geq k_1$}.\cr } \right. $$ We also determine the cases of equality. We then obtain a more general inequality, a special case of which is a sharp bound for cross-intersecting families of permutations.