Tutte polynomials of appropriate Cayley graphs - MathOverflow

Tutte polynomials of appropriate Cayley graphs

2011-10-12T04:41:00Z

I was quite intrigued by Tutte polynomials in a recent talk I had been to. It was introduced as a polynomial associated to a undirected finite graph. For a graph $G=(V,E)$ we form the polynomial

$T_G(x,y)=\sum_{A\subseteq E} (x-1)^{k(A)-k(E)}(y-1)^{k(A)+|A|-|V|}$

where $k(A)$ is the number of components of the graph $(G,A)$.

I have heard and read about the significance of this polynomial. However, I'm completely new to combinatorics and graph theory and have no prior knowledge of what is or isn't known about these things. I have two questions which should be easy enough for the experts.

(1) Let us start with a finite group $G$, chose a presentation and consider its Cayley graph $\Gamma$. Now consider the Tutte polynomial $T_\Gamma$ of $\Gamma$. We suppose that $G$ is the fundamental group of some reasonable space $M$ (it always is $\pi_1$ of some space but what I mean here is the space is a manifold or very broadly an object where distances and volumes make sense).

Question Does the Tutte polynomial $T_\Gamma$ encode any information about the topological invariants of $M$?

(2) In my own naive way I was trying to see if anything similar (like the formula at the outset) works for infinite graphs. The existence of such a thing, at least, looks very interesting as Tutte polynomials generally have a lot of significance. If such a thing doesn't exist, one may begin to study properties of the Tutte polynomials associated to finite subgraphs of an infinite graph and analyze the asymptotics of the these properties on the poset of finite subgraphs.

Question Is there a known way to define Tutte polynomials for infinite graphs? If so, how is defined and what is known?

Question If the above answer is yes then what does $T_\Gamma$ encode about the growth of $G$ when $G$ is the fundamental group of a manifold? Note that by the $\check{S}varc$-$Milnor$ lemma this growth is asymptotic to the growth (in the sense of geometry) of the universal cover of $M$.

REMARK : I edited the first question as the growth of a finite group is not terribly interesting. The original first question should make more sense now, as presented, as the last question.

Answer by psd for Tutte polynomials of appropriate Cayley graphs

2011-10-12T05:08:57Z

Is there a known way to define Tutte polynomials for infinite graphs? If so, how is defined and what is known?

From section 9.3.2 of http://www.springerlink.com/content/h711935478607208/fulltext.pdf :

A generating function can often be thought of as a (possible infinite) polynomial whose coefficients count structures that are encoded by the exponents of the variables ... In the case of the Tutte polynomial, there are several different generating function formulations, each of which has its advantages.

Answer by Bruce Westbury for Tutte polynomials of appropriate Cayley graphs

2011-10-12T07:12:36Z

The Tutte polynomial of a finite graph has a physical interpretation as the partition function of the $q$-state Potts model on the graph. The Potts and Ising models were originally studied on the square lattice lattice and on the graph of the tiling of the plane by equilateral triangles. This means that in some sense the Tutte "polynomial" of these two infinite graphs has been intensively studied. Another example that is in Baxter's book as a "toy model" is the Cayley graph of a free group.