Intersecting and cross-intersecting families of labeled sets (Q1010662)

Summary: A family \({\mathcal A}\) of sets is said to be intersecting if any two sets in \({\mathcal A}\) intersect. Families \({\mathcal A}_1,\dots, {\mathcal A}_p\) are said to be cross-intersecting if, for any \(i, j \in \{1,\dots, p\}\) such that \(i \neq j\), any set in \({\mathcal A}_i\) intersects any set in \({\mathcal A}_j\). For \({\mathbf k} = (k_1,\dots, k_n) \in {\mathbb N}^n\), \(2 \leq k_1 \leq \cdots \leq k_n\), let \({\mathcal L}_{\mathbf {k}}\) be the family of labeled \(n\)-sets given by \({\mathcal L}_{\mathbf {k}} := \{\{(1,l_1),\dots, (n,l_n)\} \colon l_i \in \{1,\dots, k_i\}, i = 1,\dots, n\}\). We point out a relationship between intersecting families and cross-intersecting families of labeled sets, and we show that, if \({\mathcal A}_1,\dots, {\mathcal A}_p\) are cross-intersecting sub-families of \({\mathcal L}_{\mathbf {k}}\), then \[ \sum_{j = 1}^p |\mathcal A_j| \leq \begin{cases} k_1k_2\cdots k_n & \text{if }p \leq k_1;\\ pk_2\cdots k_n & \text{if } p \geq k_1\end{cases}. \] 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.