A deletion-contraction formula and monotonicity properties for the polymatroid Tutte polynomial

Abstract

The Tutte polynomial is a fundamental invariant of matroids. The polymatroid Tutte polynomial ${\mathcal{T}}_P(x,y)$, introduced by Bernardi, Kálmán, and Postnikov, is an extension of the classical Tutte polynomial from matroids to polymatroids $P$. In this paper, we first obtain a deletion-contraction formula for ${\mathcal{T}}_P(x,y)$. Then we prove two natural properties of coefficientwise monotonicity, one for containment and one for minors, both for the interior polynomial $x^n{\mathcal{T}}_P(x^{-1},1)$ and the exterior polynomial $y^n{\mathcal{T}}_P(1,y^{-1})$, where $P$ is a polymatroid over $[n]$. We show by an example that these monotonicity properties do not extend to ${\mathcal{T}}_P(x,y)$. Using deletion-contraction, we obtain formulas for the coefficients of terms of degree $n-1$ in ${\mathcal{T}}_P(x,y)$. Finally, we characterize hypergraphs $\mathcal{H}=(V,E)$ such that the coefficient of $y^k$ in the exterior polynomial of the associated polymatroid $P_{\mathcal{H}}$ attains its maximal value $\left(\genfrac{}{}{0ex}{}{|V|+k-2}{k}\right)$ for all $k$ up to some bound.

22 pages, 2 figures, Published in International Mathematics Research Notices