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

DOI10.2140/INVOLVE.2015.8.119zbMATH Open1309.05176arXiv1311.7062OpenAlexW2078612831MaRDI QIDQ2340142FDOQ2340142

Authors: Adam Dyck, K. Meagher 

Publication date: 16 April 2015

Published in: Involve (Search for Journal in Brave)

Abstract: A $kell$-subset partition, or $(k,ell)$-subpartition, is a $kell$-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 ErdH{o}s-Ko-Rado theorem for intersecting families of $(k,ell)$-subpartitions. We show that for $ngeqkell$, $ellgeq2$ and $kgeq3$, the largest $1$-intersecting family contains at most $$ $(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.

Full work available at URL: https://arxiv.org/abs/1311.7062

Recommendations

• An extension of the Erdős-Ko-Rado theorem to uniform set partitions
• Erdős-Ko-Rado theorems for uniform set-partition systems
• A general 2-part Erdős-Ko-Rado theorem
• Erdős-Ko-Rado theorems for set partitions with certain block size
• The Erdős-Ko-Rado theorem for small families

zbMATH Keywords

set partitionsErdős-Ko-Rado theorem

Mathematics Subject Classification ID

Partitions of sets (05A18) Extremal set theory (05D05)

Cited In (11)

• The Erdős-Ko-Rado properties of set systems defined by double partitions
• A short proof of an Erdős-Ko-Rado theorem for compositions
• Erdős-Ko-Rado theorems for uniform set-partition systems
• Rado Partition Theorem for Random Subsets of Integers
• An Erdős--Ko--Rado theorem for partial permutations
• Erdős-Ko-Rado theorems for set partitions with certain block size
• The Katona cycle proof of the Erdős-Ko-Rado theorem and its possibilities
• Intersecting integer partitions
• An Application of Polya's Enumeration Theorem to Partitions of Subsets of Positive Integers
• An extension of the Erdős-Ko-Rado theorem to uniform set partitions
• A Kruskal-Katona type theorem for integer partitions

This page was built for publication: An Erdős-Ko-Rado theorem for subset partitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2340142)