How many pop-stacks does it take to sort a permutation?

2020/12/09 by Albert, Michael, Vatter, Vincent
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2012.05275

Abstract

Pop-stacks are variants of stacks that were introduced by Avis and Newborn in 1981. Coincidentally, a 1982 result of Unger implies that every permutation of length n can be sorted by n-1 passes through a deterministic pop-stack. We give a new proof of this result inspired by Knuth's zero-one principle.

Related

• Enumerating permutations sortable by k passes through a pop-stack
• A stack and a pop stack in series
• Sorting permutations using a pop stack with a bypass
• Lower bound on the running time of Pop-Stack Sorting on a random permutation
• Permutations sortable by n-4 passes through a stack