DMTCS Proceedings, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008)

Font Size:  Small  Medium  Large

The Sorting Order on a Coxeter Group

Drew Armstrong


Let (W,S) be an arbitrary Coxeter system. For each sequence ω =(ω1,ω2,…)∈S* in the generators we define a partial order---called the ω-sorting order---on the set of group elements Wω⊆W that occur as finite subwords of ω. We show that the ω-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 &om;-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 supersolvable antimatroids and we show that these are equivalent to the class of supersolvable join-distributive lattices.

Full Text: GZIP Compressed PostScript PostScript PDF

Valid XHTML 1.0 Transitional