Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)$?

EDIT: I noticed recently that something must be wrong with the claimed formula because if $G$ is the disjoint union of $n$ isolated vertices, then $T_G(x,y) = 1$, so the righthand side becomes $t^{n-1}$; however the lefthand side is $1$. Implicitly Welsh and Merino are assuming that $G$ is connected or I do not know what is meant by the "size" of a forest.

share|improve this question
add comment

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
One more comment: the $h$-polynomial mentioned in part 1 has its coefficients going in reverse order to the $h$-polynomial mentioned in part 2. I didn't chase everything through, but I think you can recover your formula once you account for this. In particular, the extra factor of $t^{d−i}$ mentioned at the end of my answer is a remnant of this reversal. –  Patricia Hersh Nov 3 '12 at 2:46
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.