An Erdős-Ko-Rado theorem for subset partitions

Abstract

A $k\ell$-subset partition, or $(k,\ell )$-subpartition, is a $k\ell$-subset of an $n$-set that is partitioned into $\ell$ distinct classes, each of size $k$. Two $(k,\ell )$-subpartitions are said to $t$-intersect if they have at least $t$ classes in common. In this paper, we prove an Erdős-Ko-Rado theorem for intersecting families of $(k,\ell )$-subpartitions. We show that for $n\ge k\ell$, $\ell \ge 2$ and $k\ge 3$, the largest $1$-intersecting family contains at most $\frac{1}{(\ell -1)!}\left(\genfrac{}{}{0ex}{}{n-k}{k}\right)\left(\genfrac{}{}{0ex}{}{n-2k}{k}\right)\cdots \left(\genfrac{}{}{0ex}{}{n-(\ell -1)k}{k}\right)$ $(k,\ell )$-subpartitions, and that this bound is only attained by the family of $(k,\ell )$-subpartitions with a common fixed class, known as the \emph{canonical intersecting family of $(k,\ell )$-subpartitions}. Further, provided that $n$ is sufficiently large relative to $k,\ell$ and $t$, the largest $t$-intersecting family is the family of $(k,\ell )$-subpartitions that contain a common set of $t$ fixed classes.

arXiv comment10 pages