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.

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, $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}, publisher = {MathOA foundation}, volume = {3}, number = {5}, year = {2020}, pages = {1099-1139}, 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