EL-labelings and canonical spanning trees for subword complexes
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 t...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2013-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/2328/pdf |
| _version_ | 1797270290480234496 |
|---|---|
| author | Vincent Pilaud Christian Stump |
| author_facet | Vincent Pilaud Christian Stump |
| author_sort | Vincent Pilaud |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T02:01:55Z |
| format | Article |
| id | doaj.art-8074672a06074524a9f6a9a2269c0edf |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:01:55Z |
| publishDate | 2013-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-8074672a06074524a9f6a9a2269c0edf2024-03-07T14:52:36ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502013-01-01DMTCS Proceedings vol. AS,...Proceedings10.46298/dmtcs.23282328EL-labelings and canonical spanning trees for subword complexesVincent Pilaud0https://orcid.org/0000-0002-2070-9223Christian Stump1Laboratoire d'informatique de l'École polytechnique [Palaiseau]Institut für Algebra, Zahlentheorie und Diskrete MathematikWe 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.https://dmtcs.episciences.org/2328/pdfel-labelingssubword complexesspanning treesexhaustive generationmöbius function.[info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | Vincent Pilaud Christian Stump EL-labelings and canonical spanning trees for subword complexes Discrete Mathematics & Theoretical Computer Science el-labelings subword complexes spanning trees exhaustive generation möbius function. [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| title | EL-labelings and canonical spanning trees for subword complexes |
| title_full | EL-labelings and canonical spanning trees for subword complexes |
| title_fullStr | EL-labelings and canonical spanning trees for subword complexes |
| title_full_unstemmed | EL-labelings and canonical spanning trees for subword complexes |
| title_short | EL-labelings and canonical spanning trees for subword complexes |
| title_sort | el labelings and canonical spanning trees for subword complexes |
| topic | el-labelings subword complexes spanning trees exhaustive generation möbius function. [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/2328/pdf |
| work_keys_str_mv | AT vincentpilaud ellabelingsandcanonicalspanningtreesforsubwordcomplexes AT christianstump ellabelingsandcanonicalspanningtreesforsubwordcomplexes |