The Tutte polynomial is a classical tool in combinatorics that encodes structural information about graphs, such as the number of spanning trees, colorings, and network reliability properties. It satisfies elegant recursive rules and connects to statistical physics models like the Potts model. However, graphs only capture pairwise relationships between objects, while hypergraphs generalize this by allowing edges (called hyperedges) to connect any number of vertices at once. This paper constructs a new Tutte polynomial specifically designed for hypergraphs, filling a gap in the existing theory.
The new polynomial, called T_HG, satisfies several important properties that make it a genuine generalization of the classical theory. It obeys deletion-contraction rules, meaning you can compute it by systematically removing or collapsing hyperedges, staying within the world of hypergraphs throughout. It also respects natural symmetries like duality and multiplicativity. The paper additionally introduces a companion polynomial for objects called k-polymatroids, which are algebraic structures that generalize matroids and arise naturally from hypergraphs. This companion polynomial satisfies an even stronger universality property, meaning it is in some sense the most general invariant obeying deletion-contraction rules in that setting.
The paper also connects T_HG to statistical physics, particularly to generalizations of the Potts model and the random cluster model for hypergraphs, which describe systems of interacting particles that can be in multiple states. These models are well-studied on ordinary graphs, and the paper carefully examines how different hypergraph versions of them relate to T_HG. Finally, the authors compare their polynomial to an earlier hypergraph Tutte polynomial by Bernardi, Kalman, and Postnikov, showing that neither one is strictly more powerful than the other at distinguishing hypergraphs. As a notable consequence, they resolve an open question by showing that the characteristic polynomial, a fundamental algebraic invariant, cannot in general be recovered from the Bernardi-Kalman-Postnikov polynomial.