$h^*$-vectors of graph polytopes using activities of dissecting spanning trees
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914913017921536 |
|---|---|
| author | Kálmán, Tamás Tóthmérész, Lilla |
| author_facet | Kálmán, Tamás Tóthmérész, Lilla |
| contents | Symmetric edge polytopes of graphs and root polytopes of semi-balanced digraphs are two classes of lattice polytopes whose $h^*$-polynomials have interesting properties and generalize important graph polynomials. For both classes of polytopes there are large, natural classes of dissections into unimodular simplices. These are such that the simplices correspond to certain spanning trees.
We show that for any ``spanning tree dissection'' of the symmetric edge polytope of a graph, or the root polytope of a semi-balanced digraph, the $h^*$-polynomial of the polytope can be computed as a generating function of certain activities of the corresponding spanning trees. Apart from giving simple and flexible algorithms for computing these polynomials, our results also reveal that all dissections in question are surprisingly similar to each other: It turns out that the distributions of many statistics of spanning tree dissections are in fact independent of the actual dissection. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2203_17127 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | $h^*$-vectors of graph polytopes using activities of dissecting spanning trees Kálmán, Tamás Tóthmérész, Lilla Combinatorics 52B20, 05C31 Symmetric edge polytopes of graphs and root polytopes of semi-balanced digraphs are two classes of lattice polytopes whose $h^*$-polynomials have interesting properties and generalize important graph polynomials. For both classes of polytopes there are large, natural classes of dissections into unimodular simplices. These are such that the simplices correspond to certain spanning trees. We show that for any ``spanning tree dissection'' of the symmetric edge polytope of a graph, or the root polytope of a semi-balanced digraph, the $h^*$-polynomial of the polytope can be computed as a generating function of certain activities of the corresponding spanning trees. Apart from giving simple and flexible algorithms for computing these polynomials, our results also reveal that all dissections in question are surprisingly similar to each other: It turns out that the distributions of many statistics of spanning tree dissections are in fact independent of the actual dissection. |
| title | $h^*$-vectors of graph polytopes using activities of dissecting spanning trees |
| topic | Combinatorics 52B20, 05C31 |
| url | https://arxiv.org/abs/2203.17127 |