Stack-sorting with consecutive-pattern-avoiding stacks

DOI10.1016/J.AAM.2021.102192zbMATH Open1467.05003arXiv2008.12297OpenAlexW3136999949MaRDI QIDQ2035992FDOQ2035992

Authors: Yanyan Li 

Publication date: 28 June 2021

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Abstract: We introduce consecutive-pattern-avoiding stack-sorting maps $ext{SC}_{s}igma$, which are natural generalizations of West's stack-sorting map $s$ and natural analogues of the classical-pattern-avoiding stack-sorting maps $s_{s}igma$ recently introduced by Cerbai, Claesson, and Ferrari. We characterize the patterns $sigma$ such that $extSort(ext{SC}_{s}igma)$, the set of permutations that are sortable via the map $scircext{SC}_{s}igma$, is a permutation class, and we enumerate the sets $extSort(ext{SC}_{sigma})$ for $sigmain123,132,321$. We also study the maps $ext{SC}_{s}igma$ from a dynamical point of view, characterizing the periodic points of $ext{SC}_{s}igma$ for all $sigmain{S}_3$ and computing $ma{x}_{piin{S}_n}|ext{SC}_{s}igm{a}^{-1}(pi)|$ for all $sigmain132,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.

Full work available at URL: https://arxiv.org/abs/2008.12297

Recommendations

• Highly sorted permutations with respect to a 312-avoiding stack
• Stack-sorting preimages of permutation classes
• Sorting with pattern-avoiding stacks: the \(132\)-machine
• Stack sorting with restricted stacks
• A survey of stack sortable permutations

zbMATH Keywords

enumerationpattern avoidancediscrete dynamicspermutation classstack-sortable permutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Combinatorial dynamics (types of periodic orbits) (37E15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Combinatorics of permutations
• Patterns in permutations and words.
• 2N noncollinear points determine at least 2N directions
• A survey of stack-sorting disciplines
• Generalized permutation patterns -- a short survey
• A proof of Julian West's conjecture that the number of two-stack-sortable permutations of length \(n\) is \(2(3n)\)!/(\((n+1)\)!\((2n+1)\)!)
• Multi-static enumeration of two-stack sortable permutations
• Sorted and/or sortable permutations
• Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations
• Descents in \(t\)-sorted permutations
• Permutations sortable by \(n - 4\) passes through a stack
• A survey of consecutive patterns in permutations
• Stack-sorting preimages of permutation classes
• Title not available (Why is that?)
• Stack sorting with restricted stacks
• Modular Catalan numbers
• Further bijections to pattern-avoiding valid hook configurations
• Catalan intervals and uniquely sorted permutations
• Counting 3-stack-sortable permutations
• Preimages under the stack-sorting algorithm
• Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations
• Stack-sorting, set partitions, and Lassalle's sequence
• Young tableaux and Solitaire bulgare
• Catalan and Schröder permutations sortable by two restricted stacks
• The cycling of partitions and composition under repeated shifts
• Solution of the Bulgarian Solitaire Conjecture
• Title not available (Why is that?)
• Title not available (Why is that?)
• Generating permutations with restricted containers
• Restricted stacks as functions
• Sorting with pattern-avoiding stacks: the \(132\)-machine
• Sorting Cayley permutations with pattern-avoiding machines
• Sorting classes
• Promotion sorting
• Troupes, cumulants, and stack-sorting

Cited In (17)

• Almost proper GIT-stacks and discriminant avoidance
• Sorting twice through a stack
• Comparing algorithms for sorting with \(t\) stacks in series
• A lift of West's stack-sorting map to partition diagrams
• Stack-sorting for Coxeter groups
• Stack sorting with increasing and decreasing stacks
• Passing through a stack k times
• Foot-sorting for socks
• Highly sorted permutations with respect to a 312-avoiding stack
• Sorting Cayley permutations with pattern-avoiding machines
• Meeting covered elements in \(\nu\)-Tamari lattices
• Dynamical aspects of \(\sigma\)-machines
• A survey of stack-sorting disciplines
• Title not available (Why is that?)
• Deterministic stack-sorting for set partitions
• On a pattern sequencing problem to minimize the maximum number of open stacks
• BIJECTIVITY BETWEEN COIN-STACKS AND PERMUTATIONS AVOIDING 132-PATTERN

Uses Software

• OEIS

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2035992)