Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published August 2008 | public
Journal Article

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

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

Created:
August 22, 2023
Modified:
October 17, 2023