Intersecting and cross-intersecting families of labeled sets (Q1010662): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Latest revision as of 02:53, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Intersecting and cross-intersecting families of labeled sets |
scientific article |
Statements
Intersecting and cross-intersecting families of labeled sets (English)
0 references
7 April 2009
0 references
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.
0 references
intersecting family of sets
0 references
cross intersectin families of sets
0 references
families of labeled sets
0 references
families of permutations
0 references