Stack-sortable permutations and beyond (Q2680951)

\textit{D. E. Knuth} [The art of computer programming. Vol. 1: Fundamental algorithms. 3rd ed. Reading, MA: Addison-Wesley (1997; Zbl 0895.68055)] classified and counted permutations which can be sorted using a stack data structure. This was later generalized to permutations sorted by two iterations of the stack, also known as 2-stack-sortable. \textit{J. West} [Permutations with restricted subsequences and stack-sortable permutations. MIT (PhD thesis) (1990)] conjectured a formula for the number of 2-stack-sortable permutations and \textit{D. Zeilberger} [Discrete Math. 102, No. 1, 85--93 (1992; Zbl 0754.05006)] proved this formula. In this expository article, the author surveys the state-of-the-art in the theory of \(t\)-stack-sortable permutations for \(t \geq 2\). The key result is a decomposition lemma due to the author, which he successfully uses to establish asymptotic bounds on the number of 3-stack-sortable permutations, thereby disproving a conjecture of Bóna (see [\textit{C. Defant}, J. Comb. Theory, Ser. A 172, Article ID 105209, 26 p. (2020; Zbl 1433.05005)]). He also gives a new proof of the number of 2-stack-sortable permutations and gives nontrivial lower bounds for the number of \(t\)-stack-sortable permutations when \(t \geq 4\).