Vincent Pilaud ; Christian Stump - EL-labelings and canonical spanning trees for subword complexes

dmtcs:2328 - Discrete Mathematics & Theoretical Computer Science, January 1, 2013, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013) - https://doi.org/10.46298/dmtcs.2328
EL-labelings and canonical spanning trees for subword complexesArticle

Authors: Vincent Pilaud ORCID1; Christian Stump 2

  • 1 Laboratoire d'informatique de l'École polytechnique [Palaiseau]
  • 2 Institut für Algebra, Zahlentheorie und Diskrete Mathematik

We describe edge labelings of the increasing flip graph of a subword complex on a finite Coxeter group, and study applications thereof. On the one hand, we show that they provide canonical spanning trees of the facet-ridge graph of the subword complex, describe inductively these trees, and present their close relations to greedy facets. Searching these trees yields an efficient algorithm to generate all facets of the subword complex, which extends the greedy flip algorithm for pointed pseudotriangulations. On the other hand, when the increasing flip graph is a Hasse diagram, we show that the edge labeling is indeed an EL-labeling and derive further combinatorial properties of paths in the increasing flip graph. These results apply in particular to Cambrian lattices, in which case a similar EL-labeling was recently studied by M. Kallipoliti and H. Mühle.


Volume: DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)
Section: Proceedings
Published on: January 1, 2013
Imported on: November 21, 2016
Keywords: EL-labelings,subword complexes,spanning trees,exhaustive generation,Möbius function.,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
    Source : OpenAIRE Graph
  • Combinatorial methods, from enumerative topology to random discrete structures and compact data representations.; Funder: European Commission; Code: 208471

7 Documents citing this article

Consultation statistics

This page has been seen 505 times.
This article's PDF has been downloaded 229 times.