On cross-intersecting families of set partitions (Q1953361): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: author (P16): Item:Q389466 |
||
Property / author | |||
Property / author: Kok Bin Wong / rank | |||
Revision as of 05:28, 14 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On cross-intersecting families of set partitions |
scientific article |
Statements
On cross-intersecting families of set partitions (English)
0 references
7 June 2013
0 references
Summary: Let \(\mathcal{B}(n)\) denote the collection of all set partitions of \([n]\). Suppose \({\mathcal{A}}_1,{\mathcal{A}}_2 \subseteq \mathcal{B}(n)\) are cross-intersecting, i.e., for all \(A_1 \in {\mathcal{A}}_1\) and \(A_2 \in {\mathcal{A}}_2\), we have \(A_1 \cap A_2 \neq \varnothing\). It is proved that for sufficiently large \(n\), \(|{\mathcal{A}}_1| |{\mathcal{A}}_2| \leq B_{n-1}^2 \) where \(B_{n}\) is the \(n\)-th Bell number. Moreover, equality holds if and only if \({\mathcal{A}}_1 = {\mathcal{A}}_2\) and \({\mathcal{A}}_1\) consists of all set partitions with a fixed singleton.
0 references
cross-intersecting
0 references
Erdős-Ko-Rado
0 references
set-partitions
0 references