Bernardi gave a formula for the Tutte polynomial 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 is a generalization of to hypergraphs. We supply a Bernardi-type description of using a ribbon structure on the underlying bipartite graph . Our formula works because it is determined by the Ehrhart polynomial of the root polytope of in the same way as 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.
Revised: 2019-11-27
Accepted: 2020-05-18
Published online: 2020-10-12
Classification: 05C10, 05C31, 05C50, 05C57, 05C65
Keywords: Hypergraph, bipartite graph, ribbon structure, Tutte polynomial, interior polynomial, embedding activity, root polytope, dissection, shelling order, -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] 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] 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] 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] Universal Tutte polynomial (2020) (https://arxiv.org/pdf/2004.00683.pdf)
[5] A lattice point counting generalisation of the Tutte polynomial (2016) (https://arxiv.org/pdf/1604.00962.pdf) | Zbl 07203424
[6] Root polytopes and strong orientations of bipartite graphs (in preparation)
[7] 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] 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] A version of Tutte’s polynomial for hypergraphs, Adv. Math., Volume 244 (2013), pp. 823-873 | Article | MR 3077890 | Zbl 1283.05136
[10] 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] 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] Interior polynomial for signed bipartite graphs and the HOMFLY polynomial (https://arxiv.org/abs/1705.05063)
[13] Normal polytopes arising from finite graphs, J. Algebra, Volume 207 (1998) no. 2, pp. 409-426 | Article | MR 1644250 | Zbl 0926.52017
[14] Permutohedra, associahedra, and beyond, Int. Math. Res. Not. IMRN (2009) no. 6, pp. 1026-1106 | Article | MR 2487491 | Zbl 1162.52007
[15] 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] A contribution to the theory of chromatic polynomials, Canad. J. Math., Volume 6 (1954), pp. 80-91 | Article | MR 61366 | Zbl 0055.17101