Stack-Sorting for Coxeter Groups

DOI10.5070/C62156890arXiv2104.03215MaRDI QIDQ6364752FDOQ6364752

Authors: Colin Defant 

Publication date: 7 April 2021

Abstract: Given an essential semilattice congruence $equiv$ on the left weak order of a Coxeter group $W$, we define the Coxeter stack-sorting operator $$ by $$, where $p{i}_{d}ownarro{w}^{e}quiv(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 $$ is West's stack-sorting map. When $equiv$ is the descent congruence on $S_n$, the operator $$ 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 $$ has at most $leftlfloorfrac2(n-1)3ightfloor$ right descents; we also show that this bound is tight. We then introduce analogues of permutree congruences in types $B$ and $widetildeA$ and use them to isolate Coxeter stack-sorting operators $mathtt{s}_B$ and $widetildehspace.05cmmathtts$ that serve as canonical type-$B$ and type-$widetildeA$ 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 $widetildehspace.05cmmathtts$. For example, in type $widetildeA$, we obtain an analogue of Zeilberger's classical formula for the number of $2$-stack-sortable permutations in $S_n$.

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Lattice ideals, congruence relations (06B10) Combinatorial dynamics (types of periodic orbits) (37E15) Semilattices (06A12) Combinatorial aspects of groups and algebras (05E16)

This page was built for publication: Stack-Sorting for Coxeter Groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6364752)