Universal Tutte polynomial

2020/04/01 by Bernardi, Olivier, Kalman, Tamas, Postnikov, Alex · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2004.00683

Abstract

The Tutte polynomial is a well-studied invariant of graphs and matroids. We first extend the Tutte polynomial from graphs to hypergraphs, and more generally from matroids to polymatroids, as a two-variable polynomial. Our definition is related to previous works of Cameron and Fink and of Kálmán and Postnikov. We then define the universal Tutte polynomial \T_n, which is a polynomial of degree n in 2+(2ⁿ-1) variables that specializes to the Tutte polynomials of all polymatroids (hence all matroids) on a ground set with n elements. The universal polynomial \T_n admits three kinds of symmetries: translation invariance, S_n-invariance, and duality.

Cited by

• A recursive definition for the polymatroid Tutte polynomial
• On the coefficients of interior and exterior polynomials of polymatroids

Related

• The Tutte polynomial of some matroids
• Tutte polynomials of matroids as universal valuative invariants
• A generalization of the Tutte polynomials
• A recursive definition for the polymatroid Tutte polynomial
• Multivariate Tutte polynomials of semimatroids