A direct proof of well-definedness for the polymatroid Tutte polynomial

Abstract

For a polymatroid $P$ over $[n]$, Bernardi, Kálmán and Postnikov [\emph{Adv. Math.} 402 (2022) 108355] introduced the polymatroid Tutte polynomial ${\mathcal{T}}_P$ relying on the order $1<2<\cdots <n$ of $[n]$, which generalizes the classical Tutte polynomial from matroids to polymatroids. They proved the independence of this order by the fact that ${\mathcal{T}}_P$ is equivalent to another polynomial that only depends on $P$. In this paper, similar to the Tutte's original proof of the well-definedness of the Tutte polynomial defined by the summation over all spanning trees using activities depending on the order of edges, we give a direct and elementary proof of the well-definedness of the polymatroid Tutte polynomial.

arXiv commentPublished in Advances in Applied Mathematics