Sorting and preimages of pattern classes
FPSAC 2012, Discrete Mathematics & Theoretical Computer Science Proceedings, Volume AR, Pages 595–606, 2012
We introduce an algorithm to determine when a sorting operation, such as
stack-sort or bubble-sort, outputs a given pattern. The algorithm provides a
new proof of the description of West-2-stack-sortable permutations, that is
permutations that are completely sorted when passed twice through a stack, in
terms of patterns. We also solve the long-standing problem of describing
West-3-stack-sortable permutations. This requires a new type of generalized
permutation pattern we call a decorated pattern.
@inproceedings{claesson2012sortpreim,
author = {Claesson, Anders and {\'U}lfarsson, Henning},
title = {Sorting and preimages of pattern classes},
booktitle = {Proceedings of the 24th International Conference on Formal Power Series and Algebraic Combinatorics ({FPSAC} 2012)},
series = {Discrete Mathematics \& Theoretical Computer Science Proceedings},
volume = {AR},
pages = {595--606},
year = {2012},
doi = {10.46298/dmtcs.3066},
}
Download the paper
Presentations
Additional material
- FPSAC 2012 Extended abstract (an abstract of this paper and this paper)
This paper is a part of the following projects: