Stack-Sorting for Coxeter Groups

Given an essential semilattice congruence $\equiv$ on the left weak order of a Coxeter group $W$, we define the Coxeter stack-sorting operator ${\bf S}\equiv:W\to W$by${\bf S}\equiv(w)=w\left(\pi_\downarrow^\equiv(w)\right)^{-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 ${\mathbf{S}}_{\equiv }$ is West’s stack-sorting map. When $\equiv$ is the descent congruence on $S_n$, the operator ${\mathbf{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$hasatmost$\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 $\tilde{A}$ and use them to isolate Coxeter stack-sorting operators ${\mathtt{s}}_B$ and $\tilde{\mathtt{s}}$ that serve as canonical type-$B$ and type-$\tilde{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 $\tilde{\mathtt{s}}$. For example, in type $\tilde{A}$, we obtain an analogue of Zeilberger’s classical formula for the number of $2$-stack-sortable permutations in $S_n$.