Combinatorial Theory

Let \(W\) be an irreducible Coxeter group. We define the Coxeter pop-stack-sorting operator \(\mathsf{Pop}:W\to W\) to be the map that fixes the identity element and sends each nonidentity element \(w\) to the meet of the elements covered by \(w\) in the right weak order. When \(W\) is the symmetric group \(S_n\), \(\mathsf{Pop}\) coincides with the pop-stack-sorting map. Generalizing a theorem about the pop-stack-sorting map due to Ungar, we prove that \[\sup\limits_{w\in W}\left|O_{\mathsf{Pop}}(w)\right|=h,\] where \(h\) is the Coxeter number of \(W\) (with \(h=\infty\) if \(W\) is infinite) and \(O_f(w)\) denotes the forward orbit of \(w\) under a map \(f\). When \(W\) is finite, this result is equivalent to the statement that the maximum number of terms appearing in the Brieskorn normal form of an element of \(W\) is \(h-1\). More generally, we define a map \(f:W\to W\) to be compulsive if for every \(w\in W\), \(f(w)\) is less than or equal to \(\mathsf{Pop}(w)\) in the right weak order. We prove that if \(f\) is compulsive, then \(\sup\limits_{w\in W}|O_f(w)|\leq h\). This result is new even for symmetric groups. We prove that \(2\)-pop-stack-sortable elements in type \(B\) are in bijection with \(2\)-pop-stack-sortable permutations in type \(A\), which were enumerated by Pudwell and Smith. Claesson and Gu{\dh}mundsson proved that for each fixed nonnegative integer \(t\), the generating function that counts \(t\)-pop-stack-sortable permutations in type \(A\) is rational; we establish analogous results in types \(B\) and \(\widetilde A\).

Mathematics Subject Classifications: 05E16, 37E15, 05A05

Keywords: Pop-stack-sorting, Coxeter group, weak order, Coxeter number, compulsive map, regular language