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

Main Article Content

Andrei Asinowski Cyril Banderier Sara Billey Benjamin Hackl Svante Linusson


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.

Article Details

How to Cite
Asinowski, A., Banderier, C., Billey, S., Hackl, B., & Linusson, S. (2019). Pop-stack sorting and its image: Permutations with overlapping runs. Acta Mathematica Universitatis Comenianae, 88(3), 395-402. Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1307/672