Cheyne Homberger

Prolific Permutations: Optimizing Downsets in the Pattern Poset

Abstract:

A permutation of n letters is k-prolific if each (n-k)-subset of the letters in its one-line notation forms a unique pattern. In this paper, we study which values of n can produce such an object. We show that a k-prolific permutation requires at least k^2/2+2k letters, and we construct k-prolific permutations using only slightly more than k^2/2+2k letters, thus giving a bound for the minimal number of letters needed to form a k-prolific permutation.