ALGEBRAIC COMBINATORICS

no. 5

Hypergraph polynomials and the Bernardi process
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: 2019-01-06
Revised: 2019-11-27
Accepted: 2020-05-18
Published online: 2020-10-12
DOI: https://doi.org/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. 
@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 = {alco.centre-mersenne.org/item/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/item/ALCO_2020__3_5_1099_0/

[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 | Article | MR 3848228 | Zbl 1404.05027

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

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

[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 07203424

[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 | Article | MR 1429893 | Zbl 0876.33011

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

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

[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 | Article | MR 3659490 | Zbl 1381.57011

[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 | Article | MR 3653240 | Zbl 1378.05096

[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 | Article | MR 1644250 | Zbl 0926.52017

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

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

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