Recently O. 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 is a common extension of bijections (and their inverses) constructed by Baker and Wang between spanning trees and break divisors.
Bibtex entry:
@techreport{egres-18-16,
AUTHOR | = | {K{\'a}lm{\'a}n, Tam{\'a}s and T{\'o}thm{\'e}r{\'e}sz, Lilla}, |
TITLE | = | {Hypergraph polynomials and the Bernardi process}, |
NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2018}, |
NUMBER | = | {TR-2018-16} |