Prolific permutations and permuted packings: downsets containing many large patterns

David Bevan, Cheyne Homberger, Bridget Eileen Tenner

Research output: Contribution to journalArticle

  • 1 Citations

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.
LanguageEnglish
Pages98-121
Number of pages24
JournalJournal of Combinatorial Theory Series A
Volume153
Early online date1 Sep 2017
DOIs
StatePublished - 31 Jan 2018

Fingerprint

Packing
Diamonds
Permutation
Bijection
Strombus or kite or diamond
Notation
Subset
Line

Keywords

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

Cite this

@article{1bedd6c679a14334a0eb4520f85e1f58,
title = "Prolific permutations and permuted packings: downsets containing many large patterns",
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.",
keywords = "permutation, pattern, pattern poset, downset, prolific permutation, packing, permuted packing",
author = "David Bevan and Cheyne Homberger and Tenner, {Bridget Eileen}",
year = "2018",
month = "1",
day = "31",
doi = "10.1016/j.jcta.2017.08.006",
language = "English",
volume = "153",
pages = "98--121",
journal = "Journal of Combinatorial Theory Series A",
issn = "0097-3165",

}

Prolific permutations and permuted packings : downsets containing many large patterns. / Bevan, David; Homberger, Cheyne; Tenner, Bridget Eileen.

In: Journal of Combinatorial Theory Series A , Vol. 153, 31.01.2018, p. 98-121.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Prolific permutations and permuted packings

T2 - Journal of Combinatorial Theory Series A

AU - Bevan,David

AU - Homberger,Cheyne

AU - Tenner,Bridget Eileen

PY - 2018/1/31

Y1 - 2018/1/31

N2 - 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.

AB - 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.

KW - permutation

KW - pattern

KW - pattern poset

KW - downset

KW - prolific permutation

KW - packing

KW - permuted packing

UR - http://www.sciencedirect.com/science/journal/00973165

U2 - 10.1016/j.jcta.2017.08.006

DO - 10.1016/j.jcta.2017.08.006

M3 - Article

VL - 153

SP - 98

EP - 121

JO - Journal of Combinatorial Theory Series A

JF - Journal of Combinatorial Theory Series A

SN - 0097-3165

ER -