Describing West-3-stack-sortable permutations with permutation patterns

Abstract

We describe a new method for finding patterns in permutations that produce a given pattern after the permutation has been passed once through a stack. We use this method to describe West-3-stack-sortable permutations, that is, permutations that are sorted by three passes through a stack. We also show how the method can be applied to the bubble-sort operator. The method requires the use of mesh patterns introduced by Brändén and Claesson (2011), as well as a new type of generalized pattern we call a decorated pattern.

20 pages, 7 figures

References in corpus (1)

• Governing Singularities of Schubert Varieties

Cited by in corpus (8)

• The computational landscape of permutation patterns
• Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
• Algorithms for discovering and proving theorems about permutation patterns
• Fertility, Strong Fertility, and Postorder Wilf Equivalence
• Sorting and preimages of pattern classes
• Revstack sort, zigzag patterns, descent polynomials of $t$-revstack sortable permutations, and Steingrímsson's sorting conjecture
• Highly Sorted Permutations and Bell Numbers
• Preimages under the Stack-Sorting Algorithm