A recursive definition for the polymatroid Tutte polynomial

2025/10/13 by Guan, Xiaxia, Jin, Xian'an, Yang, Weiling
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2510.11046

Abstract

The Tutte polynomial is a significant invariant of graphs and matroids. It is well-known that it has three equivalent definitions: bases expansion, rank generating function, and deletion-contraction formula. The polymatroid Tutte polynomial \mathscrT_P generalizes the Tutte polynomial from matroids to polymatroids P. In [Adv. Math. 402 (2022) 108355.] and [J. Combin. Theory Ser. A 188 (2022) 105584], the authors provided bases expansion and rank generating function constructions for \mathscrT_P, respectively. In [Int. Math. Res. Not. 19 (2025) rnaf302], a recursive formula for \mathscrT_P was obtained. In this paper, we show that the recursive formula itself can be used to define the polymatroid Tutte polynomial independently.

Citations

• A direct proof of well-definedness for the polymatroid Tutte polynomial
• A deletion-contraction formula and monotonicity properties for the polymatroid Tutte polynomial
• Universal Tutte polynomial
• The Tutte polynomial via lattice point counting
• A Contribution to the Theory of Chromatic Polynomials

Related

• A direct proof of well-definedness for the polymatroid Tutte polynomial
• A deletion-contraction formula and monotonicity properties for the polymatroid Tutte polynomial
• The Tutte polynomial of some matroids
• On the polymatroid Tutte polynomial
• Universal Tutte polynomial