An Erd\H{o}s-Ko-Rado theorem for subset partitions
| Autor: | Dyck, Adam, Meagher, Karen |
|---|---|
| Rok vydání: | 2013 |
| Předmět: | |
| Zdroj: | Involve 8 (2015) 119-127 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.2140/involve.2015.8.119 |
| Popis: | 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\H{o}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 largest $1$-intersecting family contains at most $\frac{1}{(\ell-1)!}\binom{n-k}{k}\binom{n-2k}{k}\cdots\binom{n-(\ell-1)k}{k}$ $(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. Comment: 10 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|