Combinatorial Theory

Given an essential semilattice congruence \(\equiv\) on the left weak order of a \linebreak Coxeter group \(W\), we define the Coxeter stack-sorting operator \({\bf S}_\equiv:W\to W\) by \({{\bf S}_\equiv(w)=w\big(\pi_\downarrow^\equiv(w)\big)^{-1}}\), where \(\pi_\downarrow^\equiv(w)\) is the unique minimal element of the congruence class of \(\equiv\) containing \(w\). When \(\equiv\) is the sylvester congruence on the symmetric group \(S_n\), the operator \({\bf S}_\equiv\) is West's stack-sorting map. When \(\equiv\) is the descent congruence on \(S_n\), the operator \({\bf S}_\equiv\) is the pop-stack-sorting map. We establish several general results about Coxeter stack-sorting operators, especially those acting on symmetric groups. For example, we prove that if \(\equiv\) is an essential lattice congruence on \(S_n\), then every permutation in the image of \({\bf S}_\equiv\) has at most \(\left\lfloor\frac{2(n-1)}{3}\right\rfloor\) right descents; we also show that this bound is tight. We then introduce analogues of permutree congruences in types \(B\) and \(\widetilde A\) and use them to isolate Coxeter stack-sorting operators \(\mathtt{s}_B\) and \(\widetilde{\mathtt{s}}\) that serve as canonical type-\(B\) and type-\(\widetilde A\) counterparts of West's stack-sorting map. We prove analogues of many known results about West's stack-sorting map for the new operators \(\mathtt{s}_B\) and \(\widetilde{\mathtt{s}}\). For example, in type \(\widetilde A\), we obtain an analogue of Zeilberger's classical formula for the number of \(2\)-stack-sortable permutations in \(S_n\).

Mathematics Subject Classifications: 06A12, 06B10, 37E15, 05A05, 05E16