2025/03/08 by Ma, Tianlong, Guan, Xiaxia, Jin, Xian'an · 1 citation
#05B35 #05C31 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2503.06095
Denote the Tutte polynomial of a graph G and a matroid M by TG(x,y) and TM(x,y) respectively. TG(x,1) and TG(1,y) were generalized to hypergraphs and further extended to integer polymatroids by Kálmán \citeKalman in 2013, called interior and exterior polynomials respectively. Let G be a (k+1)-edge connected graph of order n and size m, and let g=m-n+1. Guan et al. (2023) \citeGuan obtained the coefficients of TG(1,y): [yj]TG(1,y)=\binomm-j-1n-2 for g-k≤ j≤ g, which was deduced from coefficients of the exterior polynomial of polymatroids. Recently, Chen and Guo (2025) \citeChen further obtained [yj]TG(1,y)=\binomm-j-1n-2-∑i=k+1g-j\binomm-j-i-1n-2|ECi(G)| for g-3(k+1)/2< j≤ g, where ECi(G) denotes the set of all minimal edge cuts with i edges. In this paper, for any matroid M=(X,rk) we first obtain [yj]TM(1,y)=∑t=j|X|-r(-1)t-j\binomtjσr+t(M), where σr+t(M) denotes the number of spanning sets with r+t elements in M and r=rk(M). Moveover, the expression of [xi]TM(x,1) is obtained immediately from the duality of the Tutte polynomial. As applications of our results, we generalize the two aforementioned results on graphs to the setting of matroids. This not only resolves two open problems posed by Chen and Guo in \citeChen but also provides a purely combinatorial proof that is significantly simpler than their original proofs.