Question

In "The Potts model and the Tutte Polynomial", D.J.A. Welsh and C. Merino claim on pg. 1135, equation 18, that, \begin{align*} \sum_{i=0}^{n-1}f_i t^i = t^{n-1}T_G(1+\frac{1}{t},1) \end{align*} where $T_G(x,y)$ is the Tutte polynomial of some graph $G$ and $f_i$ denotes the number of forests of $G$ with exactly $i$ edges. Their paper is available online here.

Welsh and Merino do not give any citations or proof for this claim. Does anyone know of such a proof? Also, is there a more explicit formula for $f_i$ in terms of $T_G(x,y)$?

Answer 1

Here are two quick ways of proving this: (1) Notice that one of the many equivalent definitions of the Tutte polynomial says $$T_G(x,y)=\sum_{A\subset E}(x-1)^{k(A)-k(E)}(y-1)^{k(A)+|A|-|V|}$$ Where $A$ runs through subsets of the edges of $G$, and the function $k(A)$ measures the number of components of the graph $(V,A)$.

Here you only need consider the terms where $k(A)+|A|=|V|$, which happens precisely when $(A,V)$ is a forest!

(2) Remember that the Tutte polynomial satisfies the deletion-contraction relation $$T_{G}(x,y)=T_{G/e}(x,y)+T_{G-e}(x,y),$$ when $e$ is neither a loop nor a bridge. So you only need to show that the generating function of forests of a graph also satisfies this recurrence, as well as the "initial conditions" that it agrees with $t^{|E|-1}T_G(1+\frac{1}{t},1)$ for $G$ a tree.

Answer 2

I think the point is to combine the following three facts:

1. the specialization $T_M(x,1)$ of the Tutte polynomial for the matroid $M$ equals the $h$-polynomial of a simplicial complex known as the independence complex of the matroid. I'm pretty sure this is in the paper "The homology and shellability of geometric lattices and matroids" by Anders Björner, though I don't have that at hand at the moment. Just now, I located this formula at the Encyclopedia of Mathematics article online on the Tutte polynomial at http://www.encyclopediaofmath.org/index.php/Tutte_polynomial

2. the relationship between $h$-polynomial and $f$-polynomial of a simplicial complex, namely $\sum_{i=0}^d f_{i-1} t^{d-i} = \sum_{k=0}^d h_k (t+1)^{d-k}$

3. the fact that the $f_i$ counts $i$-dimensional faces of the independence complex of the matroid $M$, which in the case of a graphic matroid is the number of forests having exactly $i+1$ edges.

I am assuming that $n$ in your formula is the number of edges in your graph, so that $t^{n-1}(1 + 1/t)^i = t^{n-1-i}(t+1)^i = t^{d-i}(t+1)^i$ where $d$ is the dimension of the independence complex for your matroid.