Permutree sorting

Abstract

Generalizing stack sorting and $c$-sorting for permutations, we define the permutree sorting algorithm. Given two disjoint subsets $U$ and $D$ of $\{2,\dots ,n-1\}$, the $(U,D)$-permutree sorting tries to sort the permutation $\pi \in {\mathfrak{S}}_n$ and fails if and only if there are $1\le i<j<k\le n$ such that $\pi$ contains the subword $jki$ if $j\in U$ and $kij$ if $j\in D$. This algorithm is seen as a way to explore an automaton which either rejects all reduced expressions of $\pi$, or accepts those reduced expressions for $\pi$ whose prefixes are all $(U,D)$-permutree sortable.

arXiv comment18 pages, 5 figures

References in corpus (8)

• Cluster algebras II: Finite type classification
• Clusters, Coxeter-sortable elements and noncrossing partitions
• Cambrian Lattices
• Sortable elements and Cambrian lattices
• Lattice congruences of the weak order
• Cambrian Hopf Algebras
• The weak order on integer posets
• Removahedral congruences versus permutree congruences