Proofs of Conjectures about Pattern-Avoiding Linear Extensions
arXiv:1905.02309 · doi:10.23638/DMTCS-21-4-16
Abstract
After fixing a canonical ordering (or labeling) of the elements of a finite poset, one can associate each linear extension of the poset with a permutation. Some recent papers consider specific families of posets and ask how many linear extensions give rise to permutations that avoid certain patterns. We build off of two of these papers. We first consider pattern avoidance in -ary heaps, where we obtain a general result that proves a conjecture of Levin, Pudwell, Riehl, and Sandberg in a special case. We then prove some conjectures that Anderson, Egge, Riehl, Ryan, Steinke, and Vaughan made about pattern-avoiding linear extensions of rectangular posets.
arXiv comment9 pages, 2 figures
References in corpus (10)
- Patterns in Inversion Sequences I
- Pattern avoidance in binary trees
- Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations
- Stack-Sorting Preimages of Permutation Classes
- Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
- Fertility, Strong Fertility, and Postorder Wilf Equivalence
- Stack-sorting for Words
- Pattern avoidance in forests of binary shrubs
- Pattern Avoidance in Reverse Double Lists
- Supertrees