Word posets, with applications to Coxeter groups

Matthew J. Samuel
(Rutgers, the State University of New Jersey)

We discuss the theory of certain partially ordered sets that capture the structure of commutation classes of words in monoids. As a first application, it follows readily that counting words in commutation classes is #P-complete. We then apply the partially ordered sets to Coxeter groups. Some results are a proof that enumerating the reduced words of elements of Coxeter groups is #P-complete, a recursive formula for computing the number of commutation classes of reduced words, as well as stronger bounds on the maximum number of commutation classes than were previously known. This also allows us to improve the known bounds on the number of primitive sorting networks.

In Petr Ambrož, Štěpán Holub and Zuzana Masáková: Proceedings 8th International Conference Words 2011 (WORDS 2011), Prague, Czech Republic, 12-16th September 2011, Electronic Proceedings in Theoretical Computer Science 63, pp. 226–230.
Published: 17th August 2011.

ArXived at: http://dx.doi.org/10.4204/EPTCS.63.28 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org