Root polytopes and Jaeger-type dissections for directed graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2021
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914913010581504 |
|---|---|
| author | Kálmán, Tamás Tóthmérész, Lilla |
| author_facet | Kálmán, Tamás Tóthmérész, Lilla |
| contents | We associate root polytopes to directed graphs and study them by using ribbon structures. Most attention is paid to what we call the semi-balanced case, i.e., when each cycle has the same number of edges pointing in the two directions. Given a ribbon structure, we identify a natural class of spanning trees and show that, in the semi-balanced case, they induce a shellable dissection of the root polytope into maximal simplices. This allows for a computation of the $h^*$-vector of the polytope and for showing some properties of this new graph invariant, such as a product formula and that in the planar case, the $h^*$-vector is equivalent to the greedoid polynomial of the dual graph. We obtain a general recursion relation as well. We also work out the case of layer-complete directed graphs, where our method recovers a previously known triangulation. Indeed our dissection is often but not always a triangulation; we address this with a series of examples. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2105_00960 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Root polytopes and Jaeger-type dissections for directed graphs Kálmán, Tamás Tóthmérész, Lilla Combinatorics 52B20, 52B22, 05C31, 05C62, 52B40, 05C22 We associate root polytopes to directed graphs and study them by using ribbon structures. Most attention is paid to what we call the semi-balanced case, i.e., when each cycle has the same number of edges pointing in the two directions. Given a ribbon structure, we identify a natural class of spanning trees and show that, in the semi-balanced case, they induce a shellable dissection of the root polytope into maximal simplices. This allows for a computation of the $h^*$-vector of the polytope and for showing some properties of this new graph invariant, such as a product formula and that in the planar case, the $h^*$-vector is equivalent to the greedoid polynomial of the dual graph. We obtain a general recursion relation as well. We also work out the case of layer-complete directed graphs, where our method recovers a previously known triangulation. Indeed our dissection is often but not always a triangulation; we address this with a series of examples. |
| title | Root polytopes and Jaeger-type dissections for directed graphs |
| topic | Combinatorics 52B20, 52B22, 05C31, 05C62, 52B40, 05C22 |
| url | https://arxiv.org/abs/2105.00960 |