Pattern-avoidance characterization of restricted-stack-sortable permutations

From papers

Let t1t\geq 1, n0n\geq 0, and p{213,321}p\in\{213,321\}. A permutation is tt-stack-sortable if it can be sorted using tt applications of the stack-sorting operator, and it avoids a pattern if it contains no subsequence order-isomorphic to that pattern. Restricted-stack characterization conjecture. The tt-stack-sortable pp-avoiding permutations of length nn are in one-to-one correspondence with the permutations of length nn that avoid the patterns 132132 and 12(t+2)12\cdots(t+2) simultaneously. This conjecture is motivated by computational agreement with the enumerations for p{213,321}p\in\{213,321\} and is presented as a conjecture related to the 321-machine; its general validity remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Sergey Kitaev and Philip B. Zhang, “Descent generating polynomials for (n-3)- and (n-4)-stack-sortable (pattern-avoiding) permutations”, arXiv:2503.22067 (2025).

Solutions 0

No solutions have been posted yet.