2020/08/27 by Defant, Colin, Zheng, Kai
#05A05 #05A15 #37E15 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2008.12297
We introduce consecutive-pattern-avoiding stack-sorting maps SCσ, which are natural generalizations of West's stack-sorting map s and natural analogues of the classical-pattern-avoiding stack-sorting maps sσ recently introduced by Cerbai, Claesson, and Ferrari. We characterize the patterns σ such that Sort(SCσ), the set of permutations that are sortable via the map s\circSCσ, is a permutation class, and we enumerate the sets Sort(SCσ) for σ∈\123,132,321\. We also study the maps SCσ from a dynamical point of view, characterizing the periodic points of SCσ for all σ∈ S3 and computing maxπ∈ Sn|SCσ-1(π)| for all σ∈\132,213,231,312\. In addition, we characterize the periodic points of the classical-pattern-avoiding stack-sorting map s132, and we show that the maximum number of iterations of s132 needed to send a permutation in Sn to a periodic point is n-1. The paper ends with numerous open problems and conjectures.