A Deza–Frankl Type Theorem for Set Partitions

Cheng Yeaw Ku, Kok Bin Wong


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
{\mathcal F}_{2t} & =\left\{P \in \mathcal{B}(n)\ : \ \vert \mu (P)\vert\leq t\right\};\\
{\mathcal F}_{2t+1}(i_0) & =\left\{P \in \mathcal{B}(n)\ : \ \vert\mu (P)\cap ([n]\setminus \{i_0\})\vert\leq t\right\}.
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}| \leq \begin{cases} \vert {\mathcal F}_{2t} \vert, & \text{if $r=2t$};\\
\vert {\mathcal F}_{2t+1}(1) \vert, & \text{if $r=2t+1$}.
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$},
for some $i_0\in [n]$.


$t$-intersecting family, Deza-Frankl, Erdős-Ko-Rado, set partitions

Full Text: PDF