An Erdős–Ko–Rado theorem for subset partitions

Dyck, Adam; Meagher, Karen

doi:10.2140/involve.2015.8.119

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

An Erdős–Ko–Rado theorem for subset partitions

Adam Dyck and Karen Meagher

Vol. 8 (2015), No. 1, 119–127

DOI: 10.2140/involve.2015.8.119

Abstract

A $k ℓ$ -subset partition, or $(k, ℓ)$ -subpartition, is a $k ℓ$ -subset of an $n$ -set that is partitioned into $ℓ$ distinct blocks, each of size $k$ . Two $(k, ℓ)$ -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, ℓ)$ -subpartitions. We show that for $n \geq k ℓ$ , $ℓ \geq 2$ and $k \geq 3$ , the number of $(k, ℓ)$ -subpartitions in the largest $1$ -intersecting family is at most $(\binom{n - k}{k}) (\binom{n - 2 k}{k}) \dots (\binom{n - (ℓ - 1) k}{k}) ∕ (ℓ - 1)!$ , and that this bound is only attained by the family of $(k, ℓ)$ -subpartitions with a common fixed block, known as the canonical intersecting family of $(k, ℓ)$ -subpartitions. Further, provided that $n$ is sufficiently large relative to $k, ℓ$ and $t$ , the largest $t$ -intersecting family is the family of $(k, ℓ)$ -subpartitions that contain a common set of $t$ fixed blocks.

Keywords

Erdős–Ko–Rado theorem, set partitions

Mathematical Subject Classification 2010

Primary: 05D05

Milestones

Received: 3 October 2013

Revised: 9 April 2014

Accepted: 12 April 2014

Published: 10 December 2014

Communicated by Glenn Hurlbert

Authors

Adam Dyck
Department of Mathematics and Statistics University of Regina 3737 Wascana Parkway S4S 0A4 Regina SK Canada

Karen Meagher
Department of Mathematics and Statistics University of Regina 3737 Wascana Parkway S4S 0A4 Regina SK Canada

Vol. 8, No. 1, 2015