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