Fertility monotonicity and average complexity of the stack-sorting map

DOI10.1016/J.EJC.2020.103276MaRDI QIDQ2225458zbMATH OpenOpenAlexFDO

Authors Colin Defant

Publication date 8 February 2021

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

West's stack-sorting map\(t\)-stack-sortable permutation,

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial identities, bijective combinatorics (05A19)

Abstract: Let $mathcal{D}_n$ denote the average number of iterations of West's stack-sorting map $s$ that are needed to sort a permutation in $S_n$ into the identity permutation $123cdotsn$. We prove that [0.62433approxlambdaleqliminf_{n oinfty}frac{mathcal D_n}{n}leqlimsup_{n oinfty}frac{mathcal D_n}{n}leq frac{3}{5}(7-8log 2)approx 0.87289,] where $lambda$ is the Golomb-Dickman constant. Our lower bound improves upon West's lower bound of $0.23$, and our upper bound is the first improvement upon the trivial upper bound of $1$. We then show that fertilities of permutations increase monotonically upon iterations of $s$. More precisely, we prove that $|s^{-1}(sigma)|leq|s^{-1}(s(sigma))|$ for all $sigmain{S}_n$, where equality holds if and only if $sigma=123cdotsn$. This is the first theorem that manifests a law-of-diminishing-returns philosophy for the stack-sorting map that B'ona has proposed. Along the way, we note some connections between the stack-sorting map and the right and left weak orders on $S_n$.

Recommendations

• Sorting twice through a stack
• Fertility numbers
• Fertilitopes
• Stack-sortable permutations and beyond
• Fertility, Strong Fertility, and Postorder Wilf Equivalence

Cites work

• scientific article; zbMATH DE number 3722110 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• 2N noncollinear points determine at least 2N directions
• 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)\)!)
• A survey of stack sortable permutations
• A survey of stack-sorting disciplines
• Catalan intervals and uniquely sorted permutations
• Combinatorics of permutations
• Counting 3-stack-sortable permutations
• Enumerating permutations sortable by \(k\) passes through a pop-stack
• Generating functions for generating trees
• Lattice path enumeration
• Ordered Cycle Lengths in a Random Permutation
• Patterns in permutations and words.
• Permutations sortable by \(n - 4\) passes through a stack
• Postorder Preimages
• Preimages under the stack-sorting algorithm
• Revstack sort, zigzag patterns, descent polynomials of t-revstack sortable permutations, and Steingrímsson's sorting conjecture
• Stack-sorting, set partitions, and Lassalle's sequence
• Two-stack-sorting with pop stacks

Cited in

(15)

• Preimages under the bubblesort operator
• Troupes, cumulants, and stack-sorting
• Fertility numbers
• Sorting with a popqueue
• Highly sorted permutations and Bell numbers
• A lift of West's stack-sorting map to partition diagrams
• Pop-stack-sorting for Coxeter groups
• Stack-sorting for Coxeter groups
• Coxeter pop-tsack torsing
• Stack-sortable permutations and beyond
• Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
• A new lower bound for deterministic pop-stack-sorting
• Fertilitopes
• Preimages under the Queuesort algorithm
• Restricted stacks as functions

This page was built for publication: Fertility monotonicity and average complexity of the stack-sorting map

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