ALGEBRAIC COMBINATORICS

no. 5
Hypergraph polynomials and the Bernardi process
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, Japan
2 Cornell University Ithaca New York 14853-4201, USA
Algebraic Combinatorics, Volume 3 (2020) no. 5, pp. 1099-1139.

Bernardi gave a formula for the Tutte polynomial T(x,y) of a graph, based on spanning trees and activities just like the original definition, but using a fixed ribbon structure to order the set of edges in a different way for each tree. The interior polynomial I is a generalization of T(x,1) to hypergraphs. We supply a Bernardi-type description of I using a ribbon structure on the underlying bipartite graph G. Our formula works because it is determined by the Ehrhart polynomial of the root polytope of G in the same way as I is. To prove this we interpret the Bernardi process as a way of dissecting the root polytope into simplices, along with a shelling order. We also show that our generalized Bernardi process gives a common extension of bijections (and their inverses), constructed by Bernardi and further studied by Baker and Wang, between spanning trees and break divisors.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.129
Classification: 05C10, 05C31, 05C50, 05C57, 05C65
Keywords: Hypergraph, bipartite graph, ribbon structure, Tutte polynomial, interior polynomial, embedding activity, root polytope, dissection, shelling order, $h$-vector.
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, Japan
2 Cornell University Ithaca New York 14853-4201, USA
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2020__3_5_1099_0,
     author = {K\'alm\'an, Tam\'as and T\'othm\'er\'esz, Lilla},
     title = {Hypergraph polynomials and the {Bernardi} process},
     journal = {Algebraic Combinatorics},
     pages = {1099--1139},
     publisher = {MathOA foundation},
     volume = {3},
     number = {5},
     year = {2020},
     doi = {10.5802/alco.129},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.129/}
}
TY  - JOUR
AU  - Kálmán, Tamás
AU  - Tóthmérész, Lilla
TI  - Hypergraph polynomials and the Bernardi process
JO  - Algebraic Combinatorics
PY  - 2020
SP  - 1099
EP  - 1139
VL  - 3
IS  - 5
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.129/
DO  - 10.5802/alco.129
LA  - en
ID  - ALCO_2020__3_5_1099_0
ER  - 
%0 Journal Article
%A Kálmán, Tamás
%A Tóthmérész, Lilla
%T Hypergraph polynomials and the Bernardi process
%J Algebraic Combinatorics
%D 2020
%P 1099-1139
%V 3
%N 5
%I MathOA foundation
%U https://alco.centre-mersenne.org/articles/10.5802/alco.129/
%R 10.5802/alco.129
%G en
%F ALCO_2020__3_5_1099_0
Kálmán, Tamás; Tóthmérész, Lilla. Hypergraph polynomials and the Bernardi process. Algebraic Combinatorics, Volume 3 (2020) no. 5, pp. 1099-1139. doi : 10.5802/alco.129. https://alco.centre-mersenne.org/articles/10.5802/alco.129/

[1] Baker, Matthew; Wang, Yao The Bernardi process and torsor structures on spanning trees, Int. Math. Res. Not. IMRN (2018) no. 16, pp. 5120-5147 | DOI | MR | Zbl

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

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

[4] Bernardi, Olivier; Kálmán, Tamás; Postnikov, Alexander Universal Tutte polynomial (2020) (https://arxiv.org/pdf/2004.00683.pdf)

[5] Cameron, Amanda; Fink, Alex A lattice point counting generalisation of the Tutte polynomial (2016) (https://arxiv.org/pdf/1604.00962.pdf) | Zbl

[6] Frank, András; Kálmán, Tamás Root polytopes and strong orientations of bipartite graphs (in preparation)

[7] Gelfand, Israel M.; Graev, Mark I.; Postnikov, Alexander Combinatorics of hypergeometric functions associated with positive roots, The Arnold–Gelfand mathematical seminars, Birkhäuser Boston, Boston, MA, 1997, pp. 205-221 | DOI | MR | Zbl

[8] Jaeger, François A combinatorial model for the Homfly polynomial, European J. Combin., Volume 11 (1990) no. 6, pp. 549-558 | DOI | MR | Zbl

[9] Kálmán, Tamás A version of Tutte’s polynomial for hypergraphs, Adv. Math., Volume 244 (2013), pp. 823-873 | DOI | MR | Zbl

[10] 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

[11] 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

[12] Kato, Keiju Interior polynomial for signed bipartite graphs and the HOMFLY polynomial (https://arxiv.org/abs/1705.05063)

[13] Ohsugi, Hidefumi; Hibi, Takayuki Normal polytopes arising from finite graphs, J. Algebra, Volume 207 (1998) no. 2, pp. 409-426 | DOI | MR | Zbl

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

[15] Schrijver, Alexander Combinatorial optimization. Polyhedra and efficiency. Vol. B, Algorithms and Combinatorics, 24, Springer-Verlag, Berlin, 2003, p. i-xxxiv and 649–1217 (Matroids, trees, stable sets, Chapters 39–69) | MR | Zbl

[16] 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: