Prolific permutations and permuted packings : downsets containing many large patterns

Bevan, David and Homberger, Cheyne and Tenner, Bridget Eileen (2018) Prolific permutations and permuted packings : downsets containing many large patterns. Journal of Combinatorial Theory Series A, 153. pp. 98-121. ISSN 0097-3165 (https://doi.org/10.1016/j.jcta.2017.08.006)

[thumbnail of Bevan-etal-JCTSA-2017-Prolific-permutations-and-permuted-packings]
Preview
 Text. Filename: Bevan_etal_JCTSA_2017_Prolific_permutations_and_permuted_packings.pdf
Accepted Author Manuscript
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo
Download (245kB)| Preview

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. We present a complete characterization of k-prolific permutations for each k, proving that k-prolific permutations of m letters exist for every m >= k^2/2+2k+1, and that none exist of smaller size. Key to these results is a natural bijection between k-prolific permutations and certain "permuted" packings of diamonds.

CORE (COnnecting REpositories)