An Extension of the Erdős-Ko-Rado Theorem to uniform set partitions

Abstract

A $(k,\ell )$-partition is a set partition which has $\ell$ blocks each of size $k$. Two uniform set partitions $P$ and $Q$ are said to be partially $t$-intersecting if there exist blocks $P_i$ in $P$ and $Q_j$ in $Q$ such that $\left|P_i\cap Q_j\right|\ge t$. In this paper we prove a version of the Erdős-Ko-Rado theorem for partially $2$-intersecting $(k,\ell )$-partitions. In particular, we show for $\ell$ sufficiently large, the set of all $(k,\ell )$-partitions in which a block contains a fixed pair is the largest set of 2-partially intersecting $(k,\ell )$-partitions. For for $k=3$, we show this result holds for all $\ell$.

19 pages