The Sorting Order on a Coxeter Group

Armstrong, Drew

Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008) (2008).

Résumé

Let $(W,S)$ be an arbitrary Coxeter system. For each sequence $\omega =(\omega_1,\omega_2,\ldots) \in S^{\ast}$ in the generators we define a partial order― called the $\omega \mathsf{-sorting order}$ ―on the set of group elements $W_{\omega} \subseteq W$ that occur as finite subwords of $\omega$ . We show that the $\omega$-sorting order is a supersolvable join-distributive lattice and that it is strictly between the weak and strong Bruhat orders on the group. Moreover, the $\omega$-sorting order is a "maximal lattice'' in the sense that the addition of any collection of edges from the Bruhat order results in a nonlattice. Along the way we define a class of structures called $\mathsf{supersolvable}$ $\mathsf{antimatroids}$ and we show that these are equivalent to the class of supersolvable join-distributive lattices.

Détail

DOI : 10.46298/dmtcs.3602