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.

  • $\begingroup$ I am confused by your first question. All finite groups have constant growth! $\endgroup$ – Steve D Oct 12 '11 at 5:14
  • $\begingroup$ @ Steve - You're right! It's late in the night and I really meant "growth of G" for the second question. I have edited the first question. $\endgroup$ – Somnath Basu Oct 12 '11 at 5:24

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.

  • $\begingroup$ This is definitely something that partially answers my question. Do you have any good reference for these physical interpretations of the Tutte polynomial? What is the title of the book by Baxter? $\endgroup$ – Somnath Basu Oct 12 '11 at 15:40
  • 1
    $\begingroup$ MR0998375 (90b:82001) Baxter, Rodney J. Exactly solved models in statistical mechanics. $\endgroup$ – Bruce Westbury Oct 12 '11 at 17:09
  • 2
    $\begingroup$ You might also find it useful to look at the papers by Alan D. Sokal on the Tutte polynomial/Potts partition function. $\endgroup$ – Bruce Westbury Oct 12 '11 at 17:14

This does not really answer your questions, but has a somewhat similar flavor, so you might find it interesting anyway - if you have a sequence of finite graphs $G_{n}$ converging (in a suitable sense) to a potentially infinite graph $G$, then it is possible to say something about convergence of roots of many graph polynomials (like chromatic polynomial or Tutte polynomial) to a suitable limiting measure. See for example the preprint "Benjamini--Schramm continuity of root moments of graph polynomials" by Csikvári and Frenkel.


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 (http://arxiv.org/abs/0803.3079):

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.

  • $\begingroup$ I don't have the book with me and I'll try to have a look tomorrow morning. However, I don't see how this helps - I don;t mind the Tutte polynomial being a possibly infinite series. the problem arises (in the definition that I have used) when you sum over subsets $A$ of the edge set $E$. If $E$ is infinite then the coefficient of a specific $x^iy^j$ may not even make sense! $\endgroup$ – Somnath Basu Oct 12 '11 at 5:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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