Stack-sorting with consecutive-pattern-avoiding stacks

Abstract: We introduce consecutive-pattern-avoiding stack-sorting maps

e x t {S C}_{s} i g m a

, which are natural generalizations of West's stack-sorting map

s

and natural analogues of the classical-pattern-avoiding stack-sorting maps

s_{s} i g m a

recently introduced by Cerbai, Claesson, and Ferrari. We characterize the patterns

s i g m a

such that

e x t S o r t (e x t {S C}_{s} i g m a)

, the set of permutations that are sortable via the map

s c i r c e x t {S C}_{s} i g m a

, is a permutation class, and we enumerate the sets

e x t S o r t (e x t {S C}_{s i g m a})

for

s i g m a i n 123, 132, 321

. We also study the maps

e x t {S C}_{s} i g m a

from a dynamical point of view, characterizing the periodic points of

e x t {S C}_{s} i g m a

for all

s i g m a i n S_{3}

and computing

m a x_{p i i n S_{n}} | e x t {S C}_{s} i g m a^{- 1} (p i) |

for all

s i g m a i n 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.

Recommendations

Cites work

Cited in

(19)

Describes a project that uses

Uses Software

This page was built for publication: Stack-sorting with consecutive-pattern-avoiding stacks