Prolific permutations and permuted packings: downsets containing many large patterns

David Bevan, Cheyne Homberger, Bridget Eileen Tenner

Research output: Contribution to journalArticle

4 Citations (Scopus)
14 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)98-121
Number of pages24
JournalJournal of Combinatorial Theory Series A
Volume153
Early online date1 Sep 2017
DOIs
Publication statusPublished - 31 Jan 2018

Keywords

  • permutation
  • pattern
  • pattern poset
  • downset
  • prolific permutation
  • packing
  • permuted packing

Fingerprint Dive into the research topics of 'Prolific permutations and permuted packings: downsets containing many large patterns'. Together they form a unique fingerprint.

  • Cite this