2023/09/24 by Guan, Xiaxia, Jin, Xian'an, Kálmán, Tamás · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2309.13639
The Tutte polynomial is a crucial invariant of matroids. The polymatroid Tutte polynomial \mathscrTP(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 \mathscrTP(x,y). Then we prove two natural monotonicity properties, for containment and for minors of the interior polynomial xn\mathscrTP(x-1,1) and the exterior polynomial yn\mathscrTP(1,y-1), for polymatroids P over [n]. We show by a counter-example that these monotonicity properties do not extend to \mathscrTP(x,y). Using deletion-contraction, we obtain formulas for the coefficients of terms of degree n-1 in \mathscrTP(x,y). Finally, for all k≥ 0, we characterize hypergraphs H=(V,E) so that the coefficient of yk in the exterior polynomial of the associated polymatroid PH attains its maximal value \binom|V|+k-2k.