A simplicial complex of 2-stack sortable permutations (Q1867009): Difference between revisions
From MaRDI portal
Latest revision as of 09:45, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A simplicial complex of 2-stack sortable permutations |
scientific article |
Statements
A simplicial complex of 2-stack sortable permutations (English)
0 references
2 April 2003
0 references
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)].
0 references
stack-sortable permutation
0 references
simplicial complex
0 references
Hilbert series
0 references
labeled tree
0 references
0 references