Stack-Sorting with Consecutive-Pattern-Avoiding Stacks

Abstract

We introduce consecutive-pattern-avoiding stack-sorting maps ${\text{SC}}_{\ddot{I}}ƒ$, which are natural generalizations of West's stack-sorting map $s$ and natural analogues of the classical-pattern-avoiding stack-sorting maps $s_{\ddot{I}}ƒ$ recently introduced by Cerbai, Claesson, and Ferrari. We characterize the patterns $\ddot{I}ƒ$ such that $\text{Sort}({\text{SC}}_{\ddot{I}}ƒ)$, the set of permutations that are sortable via the map $s\circ {\text{SC}}_{\ddot{I}}ƒ$, is a permutation class, and we enumerate the sets $\text{Sort}({\text{SC}}_{\ddot{I}}ƒ)$ for $\ddot{I}ƒ\in \{123,132,321\}$. We also study the maps ${\text{SC}}_{\ddot{I}}ƒ$ from a dynamical point of view, characterizing the periodic points of ${\text{SC}}_{\ddot{I}}ƒ$ for all $\ddot{I}ƒ\in S_3$ and computing ${\max }_{\ddot{I}€\in S_n}|{\text{SC}}_{\ddot{I}}{ƒ}^{-1}(\ddot{I}€)|$ for all $\ddot{I}ƒ\in \{132,213,231,312\}$. In addition, we characterize the periodic points of the classical-pattern-avoiding stack-sorting map $s_{132}$, and we show that the maximum number of iterations of $s_{132}$ needed to send a permutation in $S_n$ to a periodic point is $n-1$. The paper ends with numerous open problems and conjectures.

26 pages, 2 figures