Centre for Discrete and Applicable Mathematics

 CDAM Research Report, LSE-CDAM-97-09

June 1997

The Tutte Polynomial as a Growth Function

Norman Biggs


The Tutte polynomial of a graph G can be defined as a sum taken over the set $\Sigma(G)$ of spanning trees of G:

$$ {\cal T}(G;x,y) = \sum_{T \in \Sigma(G)} x^{i(T)} y^{j(T)}, $$

where i(T) and j(T) are non-negative integers associated with the spanning tree T. Partial evaluations of the Tutte polynomial occur in a wide variety of seemingly unrelated situations: the graph-colouring polynomial and the Jones polynomial of a knot or link being just two examples. Recently it has been observed that the set $\Sigma(G)$ is in bijective correspondence with several other sets of objects associated with G. In fact all these sets are instances of an abelian group K(G), which has a natural presentation in terms of G. The main result of this paper is that the reciprocal polynomial of ${\cal T}(G;1,z)$ is the growth function ${\cal L}(z)$ of K(G) with respect to its natural presentation:

$$ z^{c} {\cal T}(G; 1,z^{-1}) = {\cal L}(z) = \sum_{g \in K(G)} z^{L(g)}, $$

where c is the cycle-rank of G and L(g) is the length of g in K(G). The basis of the proof is the observation that manipulations involving the natural set of generators and relations for K(G) correspond to moves in the so-called `dollar game' on G.

If you would like a free copy of this report, please send the number of this report, LSE-CDAM-97-09, together with your name and postal address to:
CDAM Research Reports Series
Centre for Discrete and Applicable Mathematics
London School of Economics
Houghton Street
London WC2A 2AE, U.K.
Phone: +44(0)-171-955 7732.
Fax: +44(0)-171-955 6877.
Email: info@maths.lse.ac.uk

Introduction to the CDAM Research Report Series.
CDAM Homepage.

Copyright © London School of Economics & Political Science 2005

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html