ALGEBRAIC COMBINATORICS

no. 6
h * -vectors of graph polytopes using activities of dissecting spanning trees
Kálmán, Tamás1; Tóthmérész, Lilla2
1 Department of Mathematics, Tokyo Institute of Technology, H-214, 2-12-1 Ookayama, Meguro-ku, Tokyo 152-8551 and International Institute for Sustainability with Knotted Chiral Meta Matter (WPI-SKCM 2 ), Hiroshima University, 1-3-1 Kagamiyama, Higashi-Hiroshima, Hiroshima 739-8526, Japan
2 ELTE Eötvös Loránd University and HUN-REN–ELTE Egerváry Research Group on Combinatorial Optimization 1117, Pázmány Péter sétány 1/C, Budapest, Hungary
Algebraic Combinatorics, Volume 6 (2023) no. 6, pp. 1637-1651.

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 types of polytopes there is a large, natural class 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: the distributions of many statistics of spanning tree dissections are in fact independent of the actual dissection.

Received:
Accepted:
Published online:
DOI: 10.5802/alco.318
Classification: 52B20, 05C31
Keywords: symmetric edge polytope, root polytope, $h^*$-vector, activity
Kálmán, Tamás 1; Tóthmérész, Lilla 2

1 Department of Mathematics, Tokyo Institute of Technology, H-214, 2-12-1 Ookayama, Meguro-ku, Tokyo 152-8551 and International Institute for Sustainability with Knotted Chiral Meta Matter (WPI-SKCM 2 ), Hiroshima University, 1-3-1 Kagamiyama, Higashi-Hiroshima, Hiroshima 739-8526, Japan
2 ELTE Eötvös Loránd University and HUN-REN–ELTE Egerváry Research Group on Combinatorial Optimization 1117, Pázmány Péter sétány 1/C, Budapest, Hungary
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2023__6_6_1637_0,
     author = {K\'alm\'an, Tam\'as and T\'othm\'er\'esz, Lilla},
     title = {$h^*$-vectors of graph polytopes using activities of dissecting spanning trees},
     journal = {Algebraic Combinatorics},
     pages = {1637--1651},
     publisher = {The Combinatorics Consortium},
     volume = {6},
     number = {6},
     year = {2023},
     doi = {10.5802/alco.318},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.318/}
}
TY  - JOUR
AU  - Kálmán, Tamás
AU  - Tóthmérész, Lilla
TI  - $h^*$-vectors of graph polytopes using activities of dissecting spanning trees
JO  - Algebraic Combinatorics
PY  - 2023
SP  - 1637
EP  - 1651
VL  - 6
IS  - 6
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.318/
DO  - 10.5802/alco.318
LA  - en
ID  - ALCO_2023__6_6_1637_0
ER  - 
%0 Journal Article
%A Kálmán, Tamás
%A Tóthmérész, Lilla
%T $h^*$-vectors of graph polytopes using activities of dissecting spanning trees
%J Algebraic Combinatorics
%D 2023
%P 1637-1651
%V 6
%N 6
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.318/
%R 10.5802/alco.318
%G en
%F ALCO_2023__6_6_1637_0
Kálmán, Tamás; Tóthmérész, Lilla. $h^*$-vectors of graph polytopes using activities of dissecting spanning trees. Algebraic Combinatorics, Volume 6 (2023) no. 6, pp. 1637-1651. doi : 10.5802/alco.318. https://alco.centre-mersenne.org/articles/10.5802/alco.318/

[1] Bernardi, Olivier A characterization of the Tutte polynomial via combinatorial embeddings, Ann. Comb., Volume 12 (2008) no. 2, pp. 139-153 | DOI | MR | Zbl

[2] Bernardi, Olivier Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings, Electron. J. Combin., Volume 15 (2008) no. 1, Paper no. 109, 53 pages | MR | Zbl

[3] D’Alì, Alessio; Delucchi, Emanuele; Michałek, Mateusz Many faces of symmetric edge polytopes, Electron. J. Combin., Volume 29 (2022) no. 3, Paper no. 3.24, 42 pages | MR | Zbl

[4] Higashitani, Akihiro; Jochemko, Katharina; Michałek, Mateusz Arithmetic aspects of symmetric edge polytopes, Mathematika, Volume 65 (2019) no. 3, pp. 763-784 | DOI | MR | Zbl

[5] Kálmán, Tamás; Murakami, Hitoshi Root polytopes, parking functions, and the HOMFLY polynomial, Quantum Topol., Volume 8 (2017) no. 2, pp. 205-248 | DOI | MR | Zbl

[6] Kálmán, Tamás; Postnikov, Alexander Root polytopes, Tutte polynomials, and a duality theorem for bipartite graphs, Proc. Lond. Math. Soc. (3), Volume 114 (2017) no. 3, pp. 561-588 | DOI | MR | Zbl

[7] Kálmán, Tamás; Tóthmérész, Lilla Hypergraph polynomials and the Bernardi process, Algebr. Comb., Volume 3 (2020) no. 5, pp. 1099-1139 | Numdam | MR | Zbl

[8] Kálmán, Tamás; Tóthmérész, Lilla Ehrhart theory of symmetric edge polytopes via ribbon structures, 2022 | arXiv

[9] Kálmán, Tamás; Tóthmérész, Lilla Root polytopes and Jaeger-type dissections for directed graphs, Mathematika, Volume 68 (2022) no. 4, pp. 1176-1220 | DOI | MR | Zbl

[10] Köppe, Matthias; Verdoolaege, Sven Computing parametric rational generating functions with a primal Barvinok algorithm, Electron. J. Combin., Volume 15 (2008) no. 1, Paper no. 16, 19 pages | MR | Zbl

[11] Matsui, Tetsushi; Higashitani, Akihiro; Nagazawa, Yuuki; Ohsugi, Hidefumi; Hibi, Takayuki Roots of Ehrhart polynomials arising from graphs, J. Algebraic Combin., Volume 34 (2011) no. 4, pp. 721-749 | DOI | MR | Zbl

[12] Ohsugi, Hidefumi; Tsuchiya, Akiyoshi The h * -polynomials of locally anti-blocking lattice polytopes and their γ-positivity, Discrete Comput. Geom., Volume 66 (2021) no. 2, pp. 701-722 | DOI | MR | Zbl

[13] Postnikov, Alexander Permutohedra, associahedra, and beyond, Int. Math. Res. Not. IMRN (2009) no. 6, pp. 1026-1106 | DOI | MR | Zbl

[14] Tutte, William T. A contribution to the theory of chromatic polynomials, Canad. J. Math., Volume 6 (1954), pp. 80-91 | DOI | MR | Zbl

Cited by Sources: