Pattern-avoidance characterization of restricted-stack-sortable permutations
Pattern-avoidance characterization of restricted-stack-sortable permutations
Let , , and . A permutation is -stack-sortable if it can be sorted using 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 -stack-sortable -avoiding permutations of length are in one-to-one correspondence with the permutations of length that avoid the patterns and simultaneously. This conjecture is motivated by computational agreement with the enumerations for 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
Sign in to submit a solution.
No solutions have been posted yet.