Short proof of a theorem of Brylawski on the coefficients of the Tutte polynomial

Abstract

In this short note we show that a system $M=(E,r)$ with a ground set $E$ of size $m$ and (rank) function $r:2^E\to {\mathbb{Z}}_{\ge 0}$ satisfying $r(S)\le \min (r(E),|S|)$ for every set $S\subseteq E$, the Tutte polynomial $$T_M(x,y):=\sum _{S\subseteq E}(x-1{)}^{r(E)-r(S)}(y-1{)}^{|S|-r(S)},$$ written as $T_M(x,y)={\sum }_{i,j}{t}_{ij}{x}^i{y}^j$, satisfies that for any integer $h\ge 0$, we have $$\sum _{i=0}^h\sum _{j=0}^{h-i}\left(\genfrac{}{}{0ex}{}{h-i}{j}\right)(-1{)}^j{t}_{ij}=(-1{)}^{m-r}\left(\genfrac{}{}{0ex}{}{h-r}{h-m}\right),$$ where $r=r(E)$, and we use the convention that when $h<m$, the binomial coefficient $\left(\genfrac{}{}{0ex}{}{h-r}{h-m}\right)$ is interpreted as $0$. This generalizes a theorem of Brylawski on matroid rank functions and $h<m$, and a theorem of Gordon for $h\le m$ with the same assumptions on the rank function. The proof presented here is significantly shorter than the previous ones. We only use the fact that the Tutte polynomial $T_M(x,y)$ simplifies to $(x-1{)}^{r(E)}{y}^{|E|}$ along the hyperbola $(x-1)(y-1)=1$.

arXiv comment4 pages