Prolific permutations and permuted packings: Downsets containing many large patterns

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:153

Article

Bevan, David¹  Homberger, Cheyne²  Tenner, Bridget Eileen³ 

[1] Univ Strathclyde, Dept Comp & Informat Sci, Glasgow G1 1XH, Lanark, Scotland

[2] Univ Maryland Baltimore Cty, Dept Math & Stat, Baltimore, MD 21250 USA

[3] Depaul Univ, Dept Math Sci, Chicago, IL 60614 USA

关键词: Permutation;    Pattern;    Pattern poset;    Downset;    Prolific permutation;    Packing;    Permuted packing;   

DOI  :  10.1016/j.jcta.2017.08.006

来源: Elsevier

【 摘 要 】

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. (C) 2017 Elsevier Inc. All rights reserved.

【 授权许可】

Free