2026/07/16 by Khallil Berrekkal, Joanna A. Ellis-Monaghan, Merijn Moody
#math.CO
We introduce a Tutte polynomial for hypergraphs, THG, together with Tk, a related Tutte polynomial for k-polymatroids. Both invariants admit deletion--contraction recursions that remain within their respective classes, and they are linked by the fact that THG specializes to Tk on the associated polymatroid of any (k+1)-uniform hypergraph. We show that THG satisfies several desirable Tutte type properties, including multiplicativity and duality, while Tk further admits a universality theorem, as well as a convolution product formula. In the uniform hypergraph setting, these latter results specialize back to THG. We also relate THG to hypergraph extensions of the Potts and random cluster models. In particular, we study degree dependent random cluster and Potts partition functions, as well as Grimmett's many body Potts model, and compare their relationship with THG in both the general and uniform settings. Finally, we compare THG with the polymatroid Tutte polynomial TP of Bernardi, K'alm'an, and Postnikov, showing that the two are incomparable in distinguishing power. As a consequence, we answer negatively a question raised by these authors by proving that the characteristic polynomial is not, in general, a specialization of TP.