CaltechAUTHORS
  A Caltech Library Service

Erdős–Ko–Rado theorems for permutations and set partitions

Ku, Cheng Yeaw and Renshaw, David (2008) Erdős–Ko–Rado theorems for permutations and set partitions. Journal of Combinatorial Theory. Series A, 115 (6). pp. 1008-1020. ISSN 0097-3165. https://resolver.caltech.edu/CaltechAUTHORS:20170822-155141742

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170822-155141742

Abstract

Let Sym([n]) denote the collection of all permutations of [n]={1,…,n}. Suppose A⊆Sym([n]) is a family of permutations such that any two of its elements (when written in its cycle decomposition) have at least t cycles in common. We prove that for sufficiently large n, |A|⩽(n−t)! with equality if and only if A is the stabilizer of t fixed points. Similarly, let B(n) denote the collection of all set partitions of [n] and suppose A⊆B(n) is a family of set partitions such that any two of its elements have at least t blocks in common. It is proved that, for sufficiently large n, |A|⩽B_(n−t) with equality if and only if A consists of all set partitions with t fixed singletons, where B_n is the nth Bell number.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1016/j.jcta.2007.12.004DOIArticle
http://www.sciencedirect.com/science/article/pii/S0097316508000022PublisherArticle
Additional Information:© 2008 Elsevier Inc. Received 4 June 2007, Available online 30 January 2008. We thank the anonymous referees for their comments that helped us make several improvements to this paper.
Subject Keywords:Intersecting families; Permutations; Set partitions
Issue or Number:6
Record Number:CaltechAUTHORS:20170822-155141742
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20170822-155141742
Official Citation:Cheng Yeaw Ku, David Renshaw, Erdős–Ko–Rado theorems for permutations and set partitions, Journal of Combinatorial Theory, Series A, Volume 115, Issue 6, August 2008, Pages 1008-1020, ISSN 0097-3165, https://doi.org/10.1016/j.jcta.2007.12.004. (http://www.sciencedirect.com/science/article/pii/S0097316508000022)
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:80707
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:23 Aug 2017 17:05
Last Modified:03 Oct 2019 18:34

Repository Staff Only: item control page