Vol. 8, No. 1, 2015

Download this article
Download this article For screen
For printing
Recent Issues

Volume 10
Issue 5, 721–900
Issue 4, 541–720
Issue 3, 361–539
Issue 2, 181–360
Issue 1, 1–180

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
Cover Page
Editorial Board
Editors’ Addresses
Editors’ Interests
About the Journal
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Subscriptions
Editorial Login
Author Index
Coming Soon
Contacts
 
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
An Erdős–Ko–Rado theorem for subset partitions

Adam Dyck and Karen Meagher

Vol. 8 (2015), No. 1, 119–127
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 k, 2 and k 3, the number of (k,)-subpartitions in the largest 1-intersecting family is at most nk k n2k k 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