A simplicial complex of 2-stack sortable permutations
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)].
- \(h\)-shellings and \(h\)-complexes
- A bijective census of nonseparable planar maps
- A proof of Julian West's conjecture that the number of two-stack-sortable permutations of length \(n\) is \(2(3n)\)!/(\((n+1)\)!\((2n+1)\)!)
- Hilbert polynomials in combinatorics
- scientific article; zbMATH DE number 3303654 (Why is no real title available?)
- Multi-static enumeration of two-stack sortable permutations
- On the Neggers-Stanley conjecture and the Eulerian polynomials
- Permutations with forbidden subsequences and nonseparable planar maps
- Stack words, standard Young tableaux, permutations with forbidden subsequences and planar maps
- Symmetry and unimodality in \(t\)-stack sortable permutations
- Enumerating S_n by associated transpositions and linear extensions of finite posets
- Permutations with forbidden subsequences and nonseparable planar maps
- Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations
- Troupes, cumulants, and stack-sorting
- Polyurethane toggles
- Stack-sorting preimages of permutation classes
- Counting 3-stack-sortable permutations
- Lattice paths and \((n - 2)\)-stack sortable permutations
- Generalized Stack Permutations
- Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
- Fertility, Strong Fertility, and Postorder Wilf Equivalence
- Sorting with networks of data structures
This page was built for publication: A simplicial complex of 2-stack sortable permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1867009)
