Permutations sorted by a finite and an infinite stack in series

2017/11/16 by Elder, Murray, Goh, Yoong Kuan
#05A05 #68R05 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1711.06040

Abstract

We prove that the set of permutations sorted by a stack of depth t ≥ 3 and an infinite stack in series has infinite basis, by constructing an infinite antichain. This answers an open question on identifying the point at which, in a sorting process with two stacks in series, the basis changes from finite to infinite.

Related

• Stack Sorting with Increasing and Decreasing Stacks
• An Infinite Antichain of Permutations
• A stack and a pop stack in series
• 2-Stack Sorting is polynomial
• Large infinite antichains of permutations