2021/04/07 by Defant, Colin
#05A05 #05E16 #06A12 #06B10 #37E15 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2104.03215
Given an essential semilattice congruence ≡ on the left weak order of a Coxeter group W, we define the Coxeter stack-sorting operator \bf S_≡:W→ W by \bf S_≡(w)=w(π_\downarrow^≡(w))-1, where π_\downarrow^≡(w) is the unique minimal element of the congruence class of ≡ containing w. When ≡ is the sylvester congruence on the symmetric group Sn, the operator \bf S_≡ is West's stack-sorting map. When ≡ is the descent congruence on Sn, the operator \bf S_≡ 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 ≡ is an essential lattice congruence on Sn, then every permutation in the image of \bf S_≡ has at most \lfloor(2(n-1))/(3)\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 \mathttsB and \widetilde\hspace.05cm\mathtts 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 \mathttsB and \widetilde\hspace.05cm\mathtts. For example, in type \widetilde A, we obtain an analogue of Zeilberger's classical formula for the number of 2-stack-sortable permutations in Sn.