Skip to main content
Open Access Publications from the University of California

Combinatorial Theory

Combinatorial Theory banner

Stack-sorting for Coxeter groups

  • Author(s): Defant, Colin
  • et al.

Published Web Location Commons 'BY' version 4.0 license

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

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View