The sorting order on a Coxeter group

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:116

Article

Armstrong, Drew

关键词: Coxeter group;    Partial order;    Lattice;    Antimatroid;    Abstract convex geometry;    Supersolvable lattice;    Join-distributive lattice;    Catalan number;    Sorting algorithm;   

DOI  :  10.1016/j.jcta.2009.03.009

来源: Elsevier

【 摘 要 】

Let (W, S) be an arbitrary Coxeter system. For each word omega in the generators we define a partial order-called the omega-sorting order-on the set of group elements W-omega subset of W that occur as 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 Bruhat orders on the group. Moreover, the omega-sorting order is a maximal lattice in the sense that the addition of any collection of Bruhat covers 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. (C) 2009 Elsevier Inc. All rights reserved.

【 授权许可】

Free