Restricted stacks as functions

DOI10.1016/J.DISC.2021.112571MaRDI QIDQ1981702zbMATH OpenOpenAlexFDO

Authors Katalin Berlow

Publication date 6 September 2021

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

pattern avoidancepermutationstack sort

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics in computer science (68R05)

Abstract: The stack sort algorithm has been the subject of extensive study over the years. In this paper we explore a generalized version of this algorithm where instead of avoiding a single decrease, the stack avoids a set $T$ of permutations. We let $s_T$ denote this map. We classify for which sets $T$ the map $s_T$ is bijective. A corollary to this answers a question of Baril, Cerbai, Khalil, and Vajnovszki about stack sort composed with $s_{sigma,au}$, known as the $(sigma,au)$-machine. This fully classifies for which $sigma$ and $au$ the preimage of the identity under the $(sigma,au)$-machine is counted by the Catalan numbers. We also prove that the number of preimages of a permutation under the map $s_T$ is bounded by the Catalan numbers, with a shift of indices. For $T$ of size 1, we classify exactly when this bound is sharp. We also explore the periodic points and maximum number of preimages of various $s_T$ for $T$ containing two length $3$ permutations.

Recommendations

• Stack sorting with restricted stacks
• Stack-sorting preimages of permutation classes
• Stack-sorting with consecutive-pattern-avoiding stacks
• Preimages under the stack-sorting algorithm
• Stack-sortable permutations and beyond

Cites work

• Catalan and Schröder permutations sortable by two restricted stacks
• Fertility monotonicity and average complexity of the stack-sorting map
• Fertility numbers
• Fertility, Strong Fertility, and Postorder Wilf Equivalence
• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• scientific article; zbMATH DE number 2107707 (Why is no real title available?)
• Preimages under the stack-sorting algorithm
• Sorted and/or sortable permutations
• Sorting and preimages of pattern classes
• Sorting Cayley permutations with pattern-avoiding machines
• Sorting with pattern-avoiding stacks: the 132-machine
• Stack sorting with restricted stacks
• Stack-sorting, set partitions, and Lassalle's sequence
• Troupes, cumulants, and stack-sorting

Cited in

(16)

• Stack-sorting with consecutive-pattern-avoiding stacks
• Stack sorting with restricted stacks
• Functions of limited accumulation
• Sorting Cayley permutations with pattern-avoiding machines
• Stack-sorting for Coxeter groups
• Highly sorted permutations with respect to a 312-avoiding stack
• Dynamical aspects of \(\sigma\)-machines
• Foot-sorting for socks
• Deterministic stack-sorting for set partitions
• Periodic points of consecutive-pattern-avoiding stack-sorting maps
• Cyclic-pattern-avoiding stacks
• Stack-sorting with stacks avoiding vincular patterns
• Partially restricted stacks as functions
• The order of the (123, 132)-avoiding stack sort
• On a conjecture on pattern-avoiding machines
• Set partitions that require a maximum number of sorts through the aba-avoiding stack

This page was built for publication: Restricted stacks as functions

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