Asymptotics of the Average Stack-Sorting Depth

Abstract

Let ${\mathcal{D}}_n$ denote the average number of passes of the stack-sorting map $s$ required to sort a permutation in $S_n$. We use the recently introduced framework of stack-sorting diagrams and tableaux to prove that the limit ${\lim }_{n\to \infty }{\mathcal{D}}_n/n$ exists. This resolves a longstanding conjecture of West originally proposed in $1990$. As a consequence, we also provide a monotonically increasing sequence that converges to ${\lim }_{n\to \infty }{\mathcal{D}}_n/n$, improving upon Defant's lower bound of $\hat{I}»\approx 0.62433$.

8 pages, 1 figure