Pop-stack sorting and its image: Permutations with overlapping runs

Abstract

Pop-stack sorting is an important variation for sorting permutations via a stack. A single iteration of pop-stack sorting is the transformation T:Sn -> Sn that reverses all the maximal descending sequences of letters in a permutation. We investigate structural and enumerative aspects of pop-stacked permutations - the permutations that belong to the image of Sn under T. This work is a part of a project aiming to provide the full combinatorial analysis of sorting with a pop-stack, as it was successfully done for sorting with a stack (though, even in this case, some famous problems are still open). The first results already show that pop-stack sorting has a very rich combinatorial structure, and leads to surprising phenomena.