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.

18 pages, 5 figures

References in corpus (1)

• Removahedral congruences versus permutree congruences