Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. The Sorting Order on ...
Conference paper

The Sorting Order on a Coxeter Group

Drew Armstrong (1)
(1) School of Mathematics
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2007
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008)
Proceedings
DOI
10.46298/dmtcs.3602
License
https://about.hal.science/hal-authorisation-v1
National Science Foundation
0603567
PostDoctoral Research Fellowship
Indicators
632
Views
588
Downloads

The Sorting Order on a Coxeter Group

Drew Armstrong (1)
(1) School of Mathematics
Abstract
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.
Keywords
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • Coxeter group
  • join-distributive lattice
  • supersolvable lattice
  • antimatroid
  • convex geometry
Cited by

Source: OpenCitations

  • Between Weak and Bruhat: The Middle Order on Permutations

    Florence Research (University of Florence)

    Authors : Mathilde Bouvel, Luca Ferrari ORCID, Bridget Eileen Tenner ORCID

    Journal reference : Volume 41, 2025, pp.

    DOI : 10.1007/s00373-024-02885-3

  • Mask Formulas for Cograssmannian Kazhdan-Lusztig Polynomials

    arXiv (Cornell University)

    Authors : Brant Jones, Alexander Woo

    Journal reference : Volume 17, 2012, pp. 151-203

    DOI : 10.1007/s00026-012-0172-3

  • Optimum basis of finite convex geometry

    Discrete Applied Mathematics

    Authors : K. Adaricheva ORCID

    Journal reference : Volume 230, 2017, pp. 11-20

    DOI : 10.1016/j.dam.2017.06.009

  • Interval parking functions

    KU ScholarWorks (University of Kansas)

    Authors : Emma Colaric, Ryan DeMuse ORCID, Jeremy L. Martin ORCID, Mei Yin ORCID

    Journal reference : Volume 123, 2020, pp. 102129

    DOI : 10.1016/j.aam.2020.102129

  • Depth in classical Coxeter groups

    Journal of Algebraic Combinatorics

    Authors : Eli Bagno, Riccardo Biagioli, Mordechai Novick, Alexander Woo ORCID

    Journal reference : Volume 44, 2016, pp. 645-676

    DOI : 10.1007/s10801-016-0683-9

  • Word posets, with applications to Coxeter groups

    Electronic Proceedings in Theoretical Computer Science

    Authors : Matthew J. Samuel

    Journal reference : Volume 63, 2011, pp. 226-230

    DOI : 10.4204/eptcs.63.28

  • Quasiplanar Diagrams and Slim Semimodular Lattices

    SZTE Publicatio Repozitórium (University of Szeged)

    Authors : Gábor Czédli ORCID

    Journal reference : Volume 33, 2015, pp. 239-262

    DOI : 10.1007/s11083-015-9362-z

  • Quotient closed subcategories of quiver representations

    arXiv (Cornell University)

    Authors : Steffen Oppermann, Idun Reiten, Hugh Thomas

    Journal reference : Volume 151, 2014, pp. 568-602

    DOI : 10.1112/s0010437x14007623

  • Note on the description of join-distributive lattices by permutations

    arXiv (Cornell University)

    Authors : Kira Adaricheva ORCID, Gábor Czédli ORCID

    Journal reference : Volume 72, 2014, pp. 155-162

    DOI : 10.1007/s00012-014-0295-y

  • Descent polynomials for k bubble-sortable permutations of type B

    European Journal of Combinatorics

    Authors : Matthew Hyatt

    Journal reference : Volume 34, 2013, pp. 1177-1191

    DOI : 10.1016/j.ejc.2013.04.006

  • How many ways can two composition series intersect?

    Discrete Mathematics

    Authors : Gábor Czédli ORCID, László Ozsvárt, Balázs Udvari

    Journal reference : Volume 312, 2012, pp. 3523-3536

    DOI : 10.1016/j.disc.2012.08.003

  • On Scattered Convex Geometries

    Nazarbayev University Repository (Nazarbayev University)

    Authors : Kira Adaricheva ORCID, Maurice Pouzet ORCID

    Journal reference : Volume 34, 2016, pp. 523-550

    DOI : 10.1007/s11083-016-9413-0

  • Coordinatization of finite join-distributive lattices

    arXiv (Cornell University)

    Authors : Gábor Czédli

    Journal reference : Volume 71, 2014, pp. 385-404

    DOI : 10.1007/s00012-014-0282-3

  • Sorting orders, subword complexes, Bruhat order and total positivity

    Advances in Applied Mathematics

    Authors : Drew Armstrong, Patricia Hersh ORCID

    Journal reference : Volume 46, 2010, pp. 46-53

    DOI : 10.1016/j.aam.2010.09.006

  • Finite convex geometries of circles

    Discrete Mathematics

    Authors : Gábor Czédli ORCID

    Journal reference : Volume 330, 2014, pp. 61-75

    DOI : 10.1016/j.disc.2014.04.017

  • Homomesies on permutations: An analysis of maps and statistics in the FindStat database

    Mathematics of Computation

    Authors : Jennifer Elder ORCID, Nadia Lafrenière ORCID, Erin McNicholas, Jessica Striker ORCID, Amanda Welch

    Journal reference : Volume 93, 2023, pp. 921-976

    DOI : 10.1090/mcom/3866
Preview
Loading PDF preview...