TR-2018-16

Hypergraph polynomials and the Bernardi process

Tamás Kálmán, Lilla Tóthmérész



Abstract

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}
}


Last modification: 29.12.2020. Please email your comments to Tamás Király!