An extension of the Erdős-Ko-Rado theorem to uniform set partitions

Abstract

A (k,ℓ)-partition is a set partition which has ℓ 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 |P_i∩Q_j| ≥ t. In this paper we prove a version of the Erdős-Ko-Rado theorem for partially 2-intersecting (k,ℓ)-partitions. In particular, we show for ℓ sufficiently large, the set of all (k,ℓ)-partitions in which a block contains a fixed pair is the largest set of 2-partially intersecting (k,ℓ)-partitions. For for k = 3, we show this result holds for all ℓ.