A Deletion-Contraction Formula and Monotonicity Properties for the Polymatroid Tutte Polynomial

The Tutte polynomial is a fundamental invariant of matroids. The polymatroid Tutte polynomial TP(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 TP(x,y). Then we prove two natural properties of coefficientwise monotonicity, one for containment and one for minors, both for the interior polynomial xⁿTP(x⁻¹,1) and the exterior polynomial yⁿTP(1,y⁻¹), where P is a polymatroid over $[n]$. We show by an example that these monotonicity properties do not extend to TP(x,y). Using deletion-contraction, we obtain formulas for the coefficients of terms of degree $n-1$ in TP(x,y). Finally, we characterize hypergraphs H=(V,E) such that the coefficient of yᵏ in the exterior polynomial of the associated polymatroid PH attains its maximal value |V|+k-2k for all k up to some bound.