A simplicial complex of 2-stack sortable permutations (Q1867009): Difference between revisions

To stack-sort a permutation, each entry of the permutation is placed on a stack, and then entries are popped off the stack until the stack is empty or the top entry on the stack is greater than the next entry in the permutation. The process can also be defined recursively; if \(p=LnR\) with \(n\) its largest entry, then \(s(p)=s(L)s(R)n\). A permutation is \(t\)-stack sortable if \(t\) stack-sorts produce the identity permutation. Correspondences have been found between 2-stack sortable permutations and certain sets of labeled trees, Young tableaux, and planar maps. For each \(n\), and for \(t=1\) and \(t=2\), the author constructs a simplicial complex in which the \(k\)-dimensional faces are in one-to-one correspopndence with the \(t\)-stack sortable permutations of length \(n\) having \(k\) ascents. The construction uses a combinatorial bijection between 2-stack sortable permutations and labeled trees [\textit{B. Jacquard} and \textit{G. Schaeffer}, J. Comb. Theory, Ser. A 83, 1-20 (1998; Zbl 0916.05057)].