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.