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

Dyck, Adam; Meagher, Karen

Involve 8, No. 1, 119-127 (2015).

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.

MSC:

05D05	Extremal set theory
05A18	Partitions of sets

Keywords:

Erdős-Ko-Rado theorem; set partitions