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

The Tutte polynomial is a crucial invariant of matroids. The polymatroid Tutte polynomial ${\mathcal{T}}_P(x,y)$, introduced by Bernardi et al., 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 monotonicity properties, for containment and for minors of the interior polynomial $x^n{\mathcal{T}}_P(x^{-1},1)$ and the exterior polynomial $y^n{\mathcal{T}}_P(1,y^{-1})$, for polymatroids $P$ over $[n]$. We show by a counter-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, for all $k\ge 0$, we characterize hypergraphs $\mathcal{H}=(V,E)$ so that the coefficient of $y^k$ in the exterior polynomial of the associated polymatroid $P_{\mathcal{H}}$ attains its maximal value $\left(\genfrac{}{}{0px}{}{\mathrm{\mid }V\mathrm{\mid }+k-2}{k}\right)$.