A Deza-Frankl type theorem for set partitions (Q2341077)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A Deza-Frankl type theorem for set partitions |
scientific article |
Statements
A Deza-Frankl type theorem for set partitions (English)
0 references
22 April 2015
0 references
Summary: A set partition of \([n]\) is a collection of pairwise disjoint nonempty subsets (called blocks) of \([n]\) whose~union is \([n]\). Let \(\mathcal{B}(n)\) denote the family of all set partitions of \([n]\). A family \(\mathcal{A} \subseteq \mathcal{B}(n)\) is said to be \(m\)-intersecting if any two of its members have at least \(m\) blocks in common. For any set partition \(P \in \mathcal{B}(n)\), let \(\tau(P) = \{x: \{x\} \in P\}\) denote the union of its singletons. Also, let \(\mu(P) = [n] -\tau(P)\) denote the set of elements that do not appear as a singleton in \(P\). Let \[ \begin{aligned} {\mathcal F}_{2t} =\left\{P \in \mathcal{B}(n)\;: \;| \mu (P)|\leqslant t\right\};\\ {\mathcal F}_{2t+1}(i_0) =\left\{P \in \mathcal{B}(n)\;: \;| \mu (P)\cap ([n]\setminus \{i_0\})|\leqslant t\right\}. \end{aligned} \] In this paper, we show that for \(r\geq 3\), there exists a \(n_0=n_0(r)\) depending on \(r\) such that for all \(n\geq n_0\), if \(\mathcal{A} \subseteq\mathcal{B}(n)\) is \((n-r)\)-intersecting, then \[ |\mathcal{A}| \leqslant \begin{cases} | {\mathcal F}_{2t} |, \,\,\text{if}\,\, r=2t;\\ | {\mathcal F}_{2t+1}(1) |, \,\,\text{if}\,\, r=2t+1. \end{cases} \] Moreover, equality holds if and only if \[ \mathcal{A}= \begin{cases} {\mathcal F}_{2t}, \,\,\text{if}\,\, r=2t;\\ {\mathcal F}_{2t+1}(i_0), \,\,\text{if}\,\, r=2t+1, \end{cases} \] for some \(i_0\in [n]\).
0 references
\(t\)-intersecting family
0 references
Deza-Frankl
0 references
Erdős-Ko-Rado
0 references
set partitions
0 references