Describing West-3-stack-sortable permutations with permutation patterns
Séminaire Lotharingien de Combinatoire, Volume 67 (2012), Article B67d
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 Branden and Claesson (2011), as well as a
new type of generalized pattern we call a decorated pattern.
Download the paper
Presentations
- A talk given at the Computer and Information Sciences Departmental Seminar at Strathclyde University, October 2011
- A talk given at the ICE-TCS Seminar at Reykjavik University, October 2011