Universal Tutte polynomial

Abstract: The Tutte polynomial is an important matroid invariant. We will explain a natural way to extend the Tutte polynomial from matroids to polymatroids. The Tutte polynomial can then be expressed as a sum over the points of the polymatroid (this is an extension of the basis extension of the classical definition of the Tutte polynomial in terms of activities). Our definition is related to previous works of Cameron and Fink and of Kálmán and Postnikov.

One of the great properties of our Tutte polynomial is that it is polynomial in the values of the rank function of the polymatroid. In other words, we can define a "universal Tutte polynomial" $T_n$ in $2+(2^n−1)$ variables that specialize to the Tutte polynomials of all polymatroids on n elements (the $2^n-1$ extra variables correspond to the non-trivial values of the rank function).

This is joint work with Tamás Kálmán and Alex Postnikov.

commutative algebraalgebraic geometrycombinatorics

Audience: researchers in the topic

Matroids - Combinatorics, Algebra and Geometry Seminar