An Erdős-Ko-Rado theorem for subset partitions. (English) Zbl 1309.05176

Summary: A \(k\ell\)-subset partition, or \((k,\ell)\)-subpartition, is a \(k\ell\)-subset of an \(n\)-set that is partitioned into \(\ell\) distinct blocks, each of size \(k\). Two \((k,\ell)\)-subpartitions are said to \(t\)-intersect if they have at least \(t\) blocks 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 \geq k\ell\), \(\ell \geq 2\) and \(k \geq 3\), the number of \((k,\ell)\)-subpartitions in the largest 1-intersecting family is at most \(\binom{n-k}{k}\binom{n-2k}{k}\cdots\binom{n-(\ell-1)k}{k}/(\ell-1)!\), and that this bound is only attained by the family of \((k,\ell)\)-subpartitions with a common fixed block, known as the 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 blocks.


05D05 Extremal set theory
05A18 Partitions of sets
Full Text: DOI arXiv