Published August 2008
| public
Journal Article
Erdős–Ko–Rado theorems for permutations and set partitions
- Creators
- Ku, Cheng Yeaw
- Renshaw, David
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.
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.Additional details
- Eprint ID
- 80707
- DOI
- 10.1016/j.jcta.2007.12.004
- Resolver ID
- CaltechAUTHORS:20170822-155141742
- Created
-
2017-08-23Created from EPrint's datestamp field
- Updated
-
2021-11-15Created from EPrint's last_modified field