Stack-Sorting with Consecutive-Pattern-Avoiding Stacks


الملخص بالإنكليزية

We introduce consecutive-pattern-avoiding stack-sorting maps $text{SC}_sigma$, which are natural generalizations of Wests stack-sorting map $s$ and natural analogues of the classical-pattern-avoiding stack-sorting maps $s_sigma$ recently introduced by Cerbai, Claesson, and Ferrari. We characterize the patterns $sigma$ such that $text{Sort}(text{SC}_sigma)$, the set of permutations that are sortable via the map $scirctext{SC}_sigma$, is a permutation class, and we enumerate the sets $text{Sort}(text{SC}_{sigma})$ for $sigmain{123,132,321}$. We also study the maps $text{SC}_sigma$ from a dynamical point of view, characterizing the periodic points of $text{SC}_sigma$ for all $sigmain S_3$ and computing $max_{piin S_n}|text{SC}_sigma^{-1}(pi)|$ for all $sigmain{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.

تحميل البحث