Hypergraph polynomials and the Bernardi process

DOI10.5802/ALCO.129MaRDI QIDQ2004047zbMATH OpenOpenAlexFDO

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

Publication date 14 October 2020

Published in Algebraic Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1810.00812

zbMATH Keywords

\(h\)-vectorbipartite graphdissectionembedding activityhypergraphinterior polynomialribbon structureroot polytopeshelling orderTutte polynomial

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph polynomials (05C31) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Games on graphs (graph-theoretic aspects) (05C57) Hypergraphs (05C65)

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 gives a common extension of bijections (and their inverses) constructed by Baker and Wang between spanning trees and break divisors.

Recommendations

• A version of Tutte's polynomial for hypergraphs
• Root polytopes, Tutte polynomials, and a duality theorem for bipartite graphs
• The Bernardi Process and Torsor Structures on Spanning Trees
• Generalized activities and the Tutte polynomial
• A characterization of the Tutte polynomial via combinatorial embeddings

Cites work

• A characterization of the Tutte polynomial via combinatorial embeddings
• A combinatorial model for the homfly polynomial
• A Contribution to the Theory of Chromatic Polynomials
• A lattice point counting generalisation of the Tutte polynomial
• A version of Tutte's polynomial for hypergraphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• scientific article; zbMATH DE number 988665 (Why is no real title available?)
• Interior polynomial for signed bipartite graphs and the HOMFLY polynomial
• Normal polytopes arising from finite graphs
• Permutohedra, Associahedra, and Beyond
• Root polytopes, parking functions, and the HOMFLY polynomial
• Root polytopes, Tutte polynomials, and a duality theorem for bipartite graphs
• The Bernardi Process and Torsor Structures on Spanning Trees
• Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings

Cited in

(8)

• A version of Tutte's polynomial for hypergraphs
• Root polytopes and Jaeger‐type dissections for directed graphs
• h^* -vectors of graph polytopes using activities of dissecting spanning trees
• A geometric proof for the root-independence of the greedoid polynomial of Eulerian branching greedoids
• Spanning hypertrees, vertex tours and meanders
• The sandpile group of a trinity and a canonical definition for the planar Bernardi action
• Extension-lifting bijections for oriented matroids
• A framework unifying some bijections for graphs and its connection to Lawrence polytopes

This page was built for publication: Hypergraph polynomials and the Bernardi process

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2004047)