Full text of DOI:10.1063/1.533181

The Potts model and the Tutte polynomial
D. J. A. Welsh and C. Merino
Citation: J. Math. Phys. 41, 1127 (2000); doi: 10.1063/1.533181
View online: http://dx.doi.org/10.1063/1.533181
View Table of Contents: http://jmp.aip.org/resource/1/JMAPAQ/v41/i3
Published by the American Institute of Physics.
Additional information on J. Math. Phys.
Journal Homepage: http://jmp.aip.org/
Journal Information: http://jmp.aip.org/about/about_the_journal
Top downloads: http://jmp.aip.org/features/most_downloaded
Information for Authors: http://jmp.aip.org/authors
Downloaded 17 Apr 2013 to 198.91.37.2. This article is copyrighted as indicated in the abstract. Reuse of AIP content is subject to the terms at: http://jmp.aip.org/about/rights_and_permissions

JOURNAL OF MATHEMATICAL PHYSICS
VOLUME 41, NUMBER 3
MARCH 2000
The Potts model and the Tutte polynomial
D. J. A. Welsha) and C. Merinob)
Mathematical Institute, Oxford University, Oxford OX1 2HP, United Kingdom
͑Received 18 November 1999; accepted for publication 30 November 1999͒
This is an invited survey on the relation between the partition function of the Potts
model and the Tutte polynomial. On the assumption that the Potts model is more
familiar we have concentrated on the latter and its interpretations. In particular we
highlight the connections with Abelian sandpiles, counting problems on random
graphs, error correcting codes, and the Ehrhart polynomial of a zonotope. Where
possible we use the mean field and square lattice as illustrations. We also discuss in
some detail the complexity issues involved. © 2000 American Institute of Phys-
ics. ͓S0022-2488͑00͒00203-6͔
I. INTRODUCTION
The classical Potts model was introduced by Potts in 1952 and in its most basic form can be
described as follows.
Consider a finite lattice Ln of N sites or general graph G of N vertices and suppose that each
site ͑ϭvertex͒ can have associated with it a spin, which can have one of Q values. The energy
between two interacting spins is taken to be zero if the spins are the same and equal to a constant
if they are different.
In the simplest description of the Potts model with Q states 1,2,...,Q , the Hamiltonian H is
͕
͖
given by
HϭJ
1Ϫ␦ ␴ ,␴ ͒͒,
͑1͒
͑
͑
͚
i
j
iϳj
where the sum is over all nearest-neighbor pairs of sites i, j and ␴ is the spin at site i. Here J is
i
the ͑constant͒ interaction. The model is ferromagnetic when JϾ0 and antiferromagnetic if J
Ͻ0.
The probability of finding the system in state ␴ is then given by
Pr ␴ ϭeϪ␤H͑␴͒/Z,
͓ ͔
͑2͒
where Z, the normalizing constant, is the partition function and ␤ϭ1/kT, where k is Boltzmann’s
constant and T is the temperature.
Thus the partition function is
Z G;Q,K͒ϭ
exp ϪK
1Ϫ␦ ␴ ,␴ ͒͒ ,
͑3͒
͑
͑
͑
͚
͚
i
j
ͩ
ͪ
␴
iϳj
where KϭJ/kT, the summation in the exponential is over all near-neighbor pairs ͑i,j͒, and the first
summation is over all possible spin configurations.
The Ising model with zero external field is just the special case when Qϭ2 and then the spins
are usually taken to be Ϯ1.
a͒
Electronic mail: dwelsh@maths.ox.ac.uk
Electronic mail: merino@maths.ox.ac.uk
b͒
0022-2488/2000/41(3)/1127/26/$17.00
1127
© 2000 American Institute of Physics
Downloaded 17 Apr 2013 to 198.91.37.2. This article is copyrighted as indicated in the abstract. Reuse of AIP content is subject to the terms at: http://jmp.aip.org/about/rights_and_permissions

1128
J. Math. Phys., Vol. 41, No. 3, March 2000
D. J. A. Welsh and C. Merino
The Tutte polynomial is less familiar and will be precisely defined in Sec. II. However in its
basic form it is just a two-variable polynomial T(G;x,y) associated with any finite graph G. Its
relation with the classical Potts model on G as described previously is that Z(G;Q,K) as given in
͑3͒ is, up to an easy multiplicative constant, just an evaluation of T along the hyperbola
H ϵ xϪ1͒ yϪ1͒ϭQ.
͑
͑
Q
To see and remember this is not difficult. The reparametrization (Q,K)↔(x,y) is just given by
QeϪK
1ϪeϪK
eKϩQϪ1
eKϪ1
xϭ1ϩ
ϭ
,
yϭeK.
Thus the Tutte polynomial T can be regarded as a natural continuation of Z from the countable
set of hyperbolae H ,Qϭ1, 2, ..., to the whole plane.
͕
͖
Q
The interpretation is quite easy and allows an easy specification of various places of interest.
For example the following correspondences are easy to check:
Tutte polynomial
Q-state Potts
Ferromagnetism
Positive branch HϩQ of HQ
Negative branch HϪQ of HQ
Antiferromagnetism
restricted to yϾ0
High temperature both ferromagnetic
and antiferromagnetic
Portion of HQ asymptotic to
yϭ1
HϩQ asymptotic to xϭ1
Low temperature ferromagnetic
Absolute zero antiferromagnetic
xϭ1ϪQ, yϭ0
A partial extension of the Potts model is the random cluster model introduced by Fortuin and
Kasteleyn in 1972. This extends the ferromagnetic Potts model to the whole of the region QϾ0
but again this is only a part of the Tutte plane. More precisely the random cluster partition function
Z
RC(Q,p) which we define in Sec. IV corresponds to the quadrant xϾ1, yϾ1 in the Tutte plane.
In what follows we highlight some of the many other specializations of the Tutte polynomial,
concentrating on those in the region of the Potts or random cluster models or those on the
boundary of this region, notably the intriguing degenerate hyperbola H0 corresponding to Qϭ0.
We also treat in some detail a curious interpretation in terms of the weight enumerator of codes,
whenever Q is a prime power.
We close this introduction by pointing out another way of thinking of the Potts model which
is useful in what follows. This is in terms of coloring. The possible colors are the integers 1, 2, ...,
Q and the sum of the right-hand side of ͑3͒ is just a sum over all possible Q colorings of the vertex
set of G. Given a particular coloring ␴ we see that its contribution to the sum is the term
\
exp ϪK͉E B ␴͉͒
͒,
͑
͑
where we use B(␴) to denote the set of edges which are bad, that is, have end points with the
same color, under ␴.
Hence, if we write bj(G;␭) to denote the number of ␭ colorings of G in which exactly j edges
are bad, then
ϱ
͉E͉
Z G;Q,K͒ϭeϪK
b G;Q͒ eK͒j.
͑4͒
͑
͑
͑
͚
j
jϭ0
Downloaded 17 Apr 2013 to 198.91.37.2. This article is copyrighted as indicated in the abstract. Reuse of AIP content is subject to the terms at: http://jmp.aip.org/about/rights_and_permissions

J. Math. Phys., Vol. 41, No. 3, March 2000
The Potts model and the Tutte polynomial
1129
In other words, if as in Ref. 1 we define the bad coloring polynomial to be the generating
function
B G;␭,s͒ϭ
b G;␭͒sj,
͑5͒
͑6͒
͑
͑
͚
j
j
then
Z G;Q,K͒ϭeϪK E B G;Q,eK͒.
͉
͉
͑
͑
An excellent, accessible review of the Potts model can be found in Wu.2
II. THE TUTTE POLYNOMIAL
The Tutte polynomial is a polynomial in two variables x,y which can be defined for a graph,
matrix, or even more generally a matroid. Most of the interesting applications arise when the
underlying structure is a graph or a matrix, but matroids are an extremely useful vehicle for
unifying the concepts and definitions. For example each of the following is a special case of the
general problem of evaluating the Tutte polynomial of a graph ͑or matrix͒ along particular curves
of the ͑x, y͒ plane:
͑i͒
͑ii͒
the chromatic and flow polynomials of a graph;
the all terminal reliability probability of a network;
͑iii͒ the partition function of a Q-state Potts model;
͑iv͒ the Jones polynomial of an alternating knot;
͑v͒
the weight enumerator of a linear code over GF(q).
In this section we will briefly review the standard theory of the Tutte polynomial and in Sec.
V we list its well-known evaluations. The graph terminology used is standard. The matroid
terminology follows Oxley.3 Further details of many of the concepts treated here can be found in
Welsh.1
First consider the following recursive definition of the function T(G;x,y) of a graph G and
two independent variables x, y.
If G has no edges, then T(G;x,y)ϭ1, otherwise for any e෈E(G).
2.1: T(G;x,y)ϭT(GЈe ;x,y)ϩT(GeЉ ;x,y), where GeЈ denotes the deletion of the edge e from
G and GeЉ denotes the contraction of e in G, and the edge e is not a loop or an isthmus,
2.2: T(G;x,y)ϭxT(GЉe ;x,y), whenever e is an isthmus, that is an edge whose removal
increases the number of connected components,
2.3: T(G;x,y)ϭyT(GeЈ ;x,y), whenever e is a loop.
From this, it is easy to show by induction that T is in fact a two-variable polynomial in x,y,
which we call the Tutte polynomial of G.
In other words, T may be calculated recursively by choosing the edges in any order and
repeatedly using 2.1–2.3 to evaluate T. The remarkable fact is that T is well defined in the sense
that the resulting polynomial is independent of the order in which the edges are chosen.
Example: In Fig. 1 we show an example of computing the Tutte polynomial of the graph G,
that is K4 minus one edge. By adding the monomials at the bottom of Fig. 1, we get that
T(G;x,y)ϭx3ϩ2x2ϩxϩ2xyϩyϩy2.
Alternatively, and this is often the easiest way to prove properties of T, we can show that T
has expansion shown in Fig. 1.
First recall that if AʕE(G), the rank of A,r(A) is defined by
r A͒ϭ
͑
͉
V G͒
͑
͉
Ϫk A͒,
͑7͒
͑
where k(A) is the number of connected components of the graph G:A having vertex set V
ϭV(G) and edge set A.
Downloaded 17 Apr 2013 to 198.91.37.2. This article is copyrighted as indicated in the abstract. Reuse of AIP content is subject to the terms at: http://jmp.aip.org/about/rights_and_permissions

1130
J. Math. Phys., Vol. 41, No. 3, March 2000
D. J. A. Welsh and C. Merino
FIG. 1. An example of computing the Tutte polynomial recursively.
It is now straightforward to prove the following.
The Tutte polynomial T(G;x,y) can be expressed in the form
r͑E͒Ϫr͑A͒
͉A͉Ϫr͑A͒
T G;x,y͒ϭ
͑
xϪ1͒
yϪ1͒
͑
.
͑8͒
͑
͚
AʕE
One feature of the Tutte polynomial which is rather surprising in view of the states model
expansion ͑8͒ is that for any graph T has an expansion of the form
T G;x,y͒ϭ
͑
t xiyj,
i, j
͚
i, j
where the ti, j are non-negative integers. Typically the ti, j are represented in matrix form. For
example, the following table provides the matrix form for the graph K6 :
jگi
0
1
2
3
4
5
0
0
24
50
35
10
1
1
2
3
4
5
6
7
8
9
24
80
120
120
96
64
35
15
5
106
145
105
60
24
6
0
0
0
0
90
45
15
0
0
0
0
0
0
0
20
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
1
It is easy and useful to extend these ideas to matroids and hence matrices.
A matroid M is just a generalization of a matrix and can be simply defined as a pair ͑E,r͒
where E is a finite set and r is a submodular rank function mapping 2E→Z and satisfying the
conditions
Downloaded 17 Apr 2013 to 198.91.37.2. This article is copyrighted as indicated in the abstract. Reuse of AIP content is subject to the terms at: http://jmp.aip.org/about/rights_and_permissions

J. Math. Phys., Vol. 41, No. 3, March 2000
The Potts model and the Tutte polynomial
1131
0рr A͒р
͉
A
͉
,
AʕE,
͑
AʕB⇒r A͒рr B͒, and
͑
͑
r AഫB͒ϩr AപB͒рr A͒ϩr B͒, A,BʕE.
͑
͑
͑
͑
The edge set of any graph G with its associated rank function, as defined by ͑7͒, is a matroid,
but this is just a very small subclass of matroids, known as graphic matroids.
A much larger class is obtained by taking any matrix B with entries in a field F, letting E be
its set of columns and for XʕE defining the rank r(X) to be the maximum size of a linearly
independent set in X. Any abstract matroid which can be represented in this way is called repre-
sentable over F.
A matroid M is representable over every field if and only if it has a representation over the
reals by a matrix B which is totally unimodular. Such a matroid is called regular. Every graphic
matroid is regular.
*
*
*
Given Mϭ(E,r), its dual matroid is M ϭ(E,r ), where r is defined by
\
*
r
E A͒ϭ
͉
E
͉
Ϫr E͒Ϫ
͉
A
͉
ϩr A͒.
͑9͒
͑
͑
͑
Duality is of fundamental importance as it allows duality concepts to be extended to nonplanar
*
graphs. When M is the matroid of a planar graph G, M is the matroid of any planar dual graph
*
of G. However when G is not planar then M is not graphic but is still representable as a matrix.
A set X is independent if r(X)ϭ , it is a base if it is a maximal independent subset of E.
We now just extend the definition of the Tutte polynomial from graphs to matroids by
͉X͉
r͑E͒Ϫr͑A͒
͉A͉Ϫr͑A͒
T M;x,y͒ϭ
͑
xϪ1͒
yϪ1͒
͑
.
͑10͒
͑
͚
AʕE͑M͒
Much of the theory developed for graphs goes through in this more general setting and there
are many applications as we shall see. For example, routine checking shows that
*
T M;x,y͒ϭT M ;y,x͒.
͑11͒
͑
͑
*
In particular, when G is a planar graph and G is any plane dual of G, ͑11͒ becomes
*
͑
T G;x,y͒ϭT G ;y,x͒.
͑
III. INTERPRETATIONS IN TERMS OF THE ISING AND POTTS MODELS
We start this section with what it is called the ‘‘recipe theorem’’ from Oxley and Welsh.4 Its
crude interpretation is that whenever a function f on some class of matroids can be shown to
satisfy an equation of the form f(M)ϭaf(MЈe )ϩbf(MeЉ), for any e෈E(M), then f is essentially
an evaluation of the Tutte polynomial.
\
Here MeЈ is the restriction of Mϭ(E,r) to the set E e with r unchanged. The contraction
͕ ͖
*
MЉ can be defined by MЉϭ(M )Ј or more usefully by its rank function r (A)ϭr(Aഫe)
Љ
e
e
e
\
Ϫr(e) for AʕE e and is the exact analog of contraction in graphs. For matrices it corresponds
͕ ͖
to projection along the column vector e. A minor of M is any matroid N obtainable from M by a
sequence of contractions and deletions. There is also a natural definition of the direct sum of two
matroids M and N, where E(M) and E(N) are disjoint sets. The rank function of M ꢀ N is given
˙
by rM ꢀ N(AഫB)ϭrM(A)ϩrN(B) for AʕE(M) and BʕE(N). Finally, we define a loop ͑coloop͒
as a single element matroid ͕e͖ with rank function r1(e)ϭ0(rc(e)ϭ1).
The recipe theorem can now be stated as follows:
Theorem 1: Let C be a class of matroids which is closed under direct sums and the taking of
minors and suppose that f is well defined on C and satisfies
Downloaded 17 Apr 2013 to 198.91.37.2. This article is copyrighted as indicated in the abstract. Reuse of AIP content is subject to the terms at: http://jmp.aip.org/about/rights_and_permissions

1132
J. Math. Phys., Vol. 41, No. 3, March 2000
D. J. A. Welsh and C. Merino
f M͒ϭaf MЈ͒ϩbf MЉ͒, e෈E M͒,
͑12͒
͑13͒
͑
͑
͑
͑
e
e
f M ꢀ M ͒ϭf M ͒f M ͒,
͑
͑
͑
1
2
1
2
then f is given by
x0 y0
͉
͉
Ϫr͑E͒
f M͒ϭa E
br͑E͒T M;
,
,
͑
ͩ
ͪ
b
a
where x0 and y0 are the values f takes on coloops and loops, respectively.
Any invariant f which satisfies ͑12͒ and ͑13͒ is called a Tutte–Grothendieck (TG)-invariant.
Thus, what we are saying is that any TG-invariant has to have an interpretation as an evalu-
ation of the Tutte polynomial. As examples we consider the Ising and Potts models.
Consider the bad coloring polynomial defined in ͑5͒,
͉E͉
B G;␭,s͒ϭ
͑
sib G;␭͒.
͑
i
͚
iϭ0
Clearly b0(G;␭) is the chromatic polynomial of G and it is easy to check that the following
relationships hold.
3.1. If G is connected, then provided e is not a loop or coloop,
B G;␭,s͒ϭB GЈ ;␭,s͒ϩ sϪ1͒B GЉ ;␭,s͒.
͑
͑
͑
͑
e
e
3.2. B(G;␭,s)ϭsB(GЈe ;␭,s), if e is a loop.
3.3. B(G;␭,s)ϭ(sϩ␭Ϫ1)B(GЉe ;␭,s), if e is a coloop.
Combining these, we get the following by using the recipe theorem for the class of connected
graphs.
sϩ␭Ϫ1
sϪ1
͉V͉
3.4. B G;␭,s͒ϭ␭ sϪ1͒ Ϫ1T G;
,s .
͑
͑
ͩ
ͪ
Consider now the relation with the Potts model. From ͑6͒ we get
eKϩQϪ1
eKϪ1
͉
V
͉
͉ ͉
ZPotts G;Q,K͒ϭQ eKϪ1͒ Ϫ1eϪK E T G;
,eK
.
͑14͒
͑
͑
ͩ
ͪ
It is not difficult ͑with hindsight͒ to verify that T(G;x,y) can be recovered from the polyno-
mial B and therefore from the Potts partition function by using the following formula:
1
T G;x,y͒ϭ
͑
B G; xϪ1͒ yϪ1͒,y͒.
͑ ͑ ͑
͉V͉
yϪ1͒ xϪ1͒
͑
͑
For connected graphs, the classical Ising model is just the case Qϭ2 in ͑14͒. When G has k
connected components then there is an extra factor of QkϪ1 on the right-hand side of ͑14͒.
IV. THE RANDOM CLUSTER MODEL AND FERROMAGNETIC POTTS MODEL
The general random cluster model on a finite graph G was introduced by Fortuin and
Kasteleyn.5 It is a correlated bond percolation model on the edge set E of G defined by the
probability distribution,
␮ A͒ϭZϪ1
p ͒
e
1Ϫp ͒ Qk͑A͒ AʕE͒,
͑15͒
͑
͑
͑
͑
͟
͟
e
RC
ͩ
ͪͩ
ͪ
e෈A
e¹A
Downloaded 17 Apr 2013 to 198.91.37.2. This article is copyrighted as indicated in the abstract. Reuse of AIP content is subject to the terms at: http://jmp.aip.org/about/rights_and_permissions

J. Math. Phys., Vol. 41, No. 3, March 2000
The Potts model and the Tutte polynomial
1133
where k(A) is the number of connected components ͑including isolated vertices͒ of the subgraph
G:Aϭ(V,A),pe(0рpeр1) are parameters associated with each edge of G, Qу0 is a parameter
of the model, and ZRC is the normalizing constant introduced so that
␮ A͒ϭ1.
͑
͚
AʕE
Then ␮(A) is interpreted as the probability that the set of edges of G open in the random
\
cluster model is exactly the set A. The complement E A is closed.
We will sometimes use ␻(G) to denote the random configuration produced by ␮, and P to
␮
denote the associated probability distribution.
Thus, in particular, ␮(A)ϭP ␻(G)ϭA . When Qϭ1, ␮ is what Fortuin and Kasteleyn call
͕
͖
␮
a percolation model and when each of the pe are made equal, say to p, then ␮(A) is clearly seen
to be the probability that the set of open edges is A in classical ordinary bond percolation.
For an account of the many different interpretations of the random cluster model we refer to
the original paper of Fortuin and Kasteleyn5 or to Grimmett.6,7
Here we shall be concentrating on the percolation problem when each of the pe are equal, to
say p, and henceforth this will be assumed.
Thus we will be concerned with a two parameter family of probability measures ␮
ϭ␮(p,Q) where 0рpр1 and QϾ0, which are defined on the edge set of the finite graph G
ϭ(V,E) by
\
͉
͉
͉
͉
␮ A͒ϭp A q E A Qk͑A͒/ZRC
,
͑
where ZRC is the appropriate normalizing constant, and qϭ1Ϫp.
The reason for studying percolation in the random cluster model is its relation with phase
transitions via the two-point correlation function. This was pointed out first by Fortuin and Kaste-
leyn and given further prominence by Edwards and Sokal8 in connection with the Swendsen–
Wang algorithm9 for simulating the Potts model. We describe briefly the connection.
The key result is the following:
Theorem 2: For any pair of sites (vertices) i, j, and positive integer Q, the probability that ␴
i
equals ␴ in the Q-state Potts model is given by
j
1
QϪ1͒
͑
ϩ
P
i j ,
͕
͖
␮
Q
Q
where P is the random cluster measure on G given by taking pϭ1Ϫexp(ϪK), and i j is the
͕
͖
␮
event that under ␮ there is an open path from i to j.
The attractive interpretation of this is that the expression on the right-hand side can be
regarded as being made up of two components.
The first term, 1/Q, is just the probability that under a purely random Q-coloring of the
vertices of G, i and j are the same color. The second term measures the probability of long range
interaction. Thus we interpret the above as expressing an equivalence between long range spin
correlations and long range percolatory behavior.
Phase transition ͑in an infinite system͒ occurs at the onset of an infinite cluster in the random
cluster model and corresponds to the spins on the vertices of the Potts model having a long range
two-point correlation.
Thus the random cluster model can be regarded as the analytic continuation of the Potts model
to noninteger QϾ0.
It is not hard to check that the relation of the random cluster model with T is that
Qq 1
ZRC G;Q,p͒ϭpr͑E͒qr
Qk͑G͒T G;1ϩ
,
,
͑16͒
*
͑E͒
͑
ͩ
ͪ
p
q
Downloaded 17 Apr 2013 to 198.91.37.2. This article is copyrighted as indicated in the abstract. Reuse of AIP content is subject to the terms at: http://jmp.aip.org/about/rights_and_permissions

1134
J. Math. Phys., Vol. 41, No. 3, March 2000
D. J. A. Welsh and C. Merino
*
where r is the dual rank, k(G) is the number of connected components of G, and qϭ1Ϫp.
It follows that for any given QϾ0, determining the partition function ZRC reduces to deter-
mining T along the hyperbola HQ given by (xϪ1)(yϪ1)ϭQ. However, since in its physical
interpretations, p is a probability, the reparametrization means that ZRC is evaluated only along the
positive branch of this hyperbola. In other words, ZRC is the specialization of T to the quadrant
xϾ1, yϾ1.
The antiferromagnetic Ising and Potts models are contained in T along the negative branches
of the hyperbolae HQ , but do not have representations in the random cluster model. For more on
this model and its relation to T see Ref. 1, Chap. 4.
V. SOME WELL-KNOWN INVARIANTS
Having shown in detail how the Potts, Ising, and random cluster models are related to the
Tutte polynomial we now collect together some of the naturally occurring interpretations of the
Tutte polynomial. Throughout G is a graph, M is a matroid, and E will denote E(G), E(M),
respectively.
In each of the following cases, the interesting quantity ͑on the left-hand side͒ is given ͑up to
an easily determined term͒ by an evaluation of the Tutte polynomial. We shall use the phrase
‘‘specializes to’’ to indicate this.
When talking about the Tutte polynomial and Potts model, it turns out that the hyperbolas H␣
defined by
H ϭ x,y͒: xϪ1͒ yϪ1͒ϭ␣
͑
͑
͑
͕
͖
␣
seem to have a special role in the theory. We note several important specializations in the follow-
ing.
͉
͉
͉E͉
͑1͒ Along H1 , T(G;x,y)ϭx E (xϪ1)r(E)Ϫ
.
͑2͒ Along H2 , when G is a graph, T specializes to the partition function of the Ising model.
͑3͒ Along HQ , for general positive integer Q,T specializes to the partition function of the
Q-state Potts model.
͑4͒ Along HQ for any positive, not necessarily integer, Q,T specializes to the partition function
of the random cluster model discussed in Sec. IV.
͑5͒ At ͑1, 1͒, T counts the number of bases of M ͑spanning trees in a connected graph͒.
͑6͒ At ͑2, 1͒, T counts the number of independent sets of M ͑forests in a graph͒.
͑7͒ At ͑1, 2͒, T counts the number of spanning connected subgraphs of the graph G.
͑8͒ At ͑2, 0͒, T counts the number of acyclic orientations of G.10
͑9͒ Another interpretation at ͑2,0͒, and this for any real matrix was discovered by Zaslavsky.11
If H ,...,H is a set of hyperplanes in d-dimensional Euclidean space with nonempty intersec-
͕
͖
1
r
tion, then T counts the number of unbounded regions of this hyperplane arrangement.
͑10͒ At ͑0, 2͒, T counts the number of totally cyclic orientations, that is, those in which every
edge of the graph G is contained in some directed cycle.
͑11͒ At ͑1, 0͒, T counts the number of acyclic orientations with exactly one source.
͑12͒ At ͑0, 1͒, if G is a directed graph having a fixed ordering on its edges, T counts the
number of totally cyclic reorientations ␶ of G such that in each cycle of ␶ the lowest edge is not
reoriented. If G is planar, T counts the number of totally cyclic orientations in which there is no
clockwise cycle.
͑13͒ When ␭ is a positive integer T(G;1Ϫ␭,0) gives the number of ␭ colorings because, the
chromatic polynomial ␹(G;␭) is given by
r͑E͒ k͑G͒
␹ G;␭͒ϭ Ϫ1͒
␭
T G;1Ϫ␭,0͒,
͑
͑
͑
where k(G) is the number of connected components.
͑14͒ Similarly T(G;0,1Ϫ␭) counts the number of nowhere zero flows over any Abelian group
of order ␭. Then the flow polynomial F(G;␭), is given by
Downloaded 17 Apr 2013 to 198.91.37.2. This article is copyrighted as indicated in the abstract. Reuse of AIP content is subject to the terms at: http://jmp.aip.org/about/rights_and_permissions

J. Math. Phys., Vol. 41, No. 3, March 2000
The Potts model and the Tutte polynomial
1135
͉E͉Ϫr͑E͒
F G;␭͒ϭ Ϫ1͒
T G;0,1Ϫ␭͒.
͑
͑
͑
͑15͒ The ͑all terminal͒ reliability R(G;p) defined as the probability that when each edge of
the connected graph G is independently deleted with probability 1Ϫp the remaining graph stays
connected is given by
͉
͉Ϫr͑E͒
R G;p͒ϭq E
pr͑E͒T G;1,1/q͒,
͑
͑
where qϭ1Ϫp.
͑16͒ At ͑0, Ϫ2͒, if G is a four-regular graph, T counts the number of ice configurations of G.
An ice configuration of G is an orientation of the edges so that at each vertex exactly two edges
are directed in and two out. It is easy to see that this counts exactly the number of nowhere zero
three-flows on G.
͉
͉
͑17͒ T(G;Ϫ1,Ϫ1)ϭ(Ϫ1) E (Ϫ2)d(B) where B is the bicycle space of G, see Read and
Rosenstiehl.12 When G is planar it also has interpretations in terms of the Arf invariant of the
associated knot.
͑18͒ The number of forests of size i of G, fi(G), is related to T by the following:
͉V͉Ϫ1
1
͉
͉
f G͒siϭs V Ϫ1T G; ϩ1,1 .
͑
ͩ
ͪ
͚
i
s
iϭ0
͑19͒ Also, the generating function of connected subgraphs of size k of G, ck(G), is related to
T by
͉E͉Ϫ͉V͉ϩ1
1
͉
͉Ϫ͉V͉
c G͒skϭs E
ϩ1T G;1; ϩ1 .
͑
ͩ
ͪ
͚
k
s
kϭ0
͑20͒ Along Hq , when q is a prime power, for a matrix M of column vectors over GF(q), T
specializes to the weight enumerator of the linear code over GF(q), with generator matrix M.
*
Equation ͑11͒ relating T(M) to T(M ) gives the MacWilliams identity of coding theory, we
return to this in Sec. IX.
͑21͒ Along the hyperbola xyϭ1 when G is planar, T specializes to the Jones polynomial of
the alternating link or knot associated with G. This connection was first discovered by
Thistlethwaite13 and is explained in Ref. 1.
Other more specialized interpretations can be found in the survey of Brylawski and Oxley14
and the book of Welsh.1
VI. MEAN FIELD RESULTS
The mean field Potts model refers to the case where the underlying graph is the complete
graph. This has been considered by Wu2 and Kesten and Schonmann15 for the classical Potts
16
´
model, and more generally for the random cluster model by Bollobas, Grimmett, and Janson.
First, however, as a useful example to illustrate what is known, we consider the behavior of
Tn(x,y)ϭT(Kn ;,x,y) for some of the points and curves described in Sec. V.
First some easy and not so easy known evaluations.
͑1͒ Along H1 , (xϪ1)(yϪ1)ϭ1,
n
ͩ ͪ
2
x
nϪ1
Tn x,y͒ϭ
xϪ1͒
͑
.
͑
ͩ
ͪ
xϪ1
͑2͒ Tn(1,1) is the number of trees on n vertices and hence
Tn 1,1͒ϭnnϪ2
.
͑
Downloaded 17 Apr 2013 to 198.91.37.2. This article is copyrighted as indicated in the abstract. Reuse of AIP content is subject to the terms at: http://jmp.aip.org/about/rights_and_permissions

1136
J. Math. Phys., Vol. 41, No. 3, March 2000
D. J. A. Welsh and C. Merino
͑3͒ The number of acyclic orientations is
Tn 2,0͒ϭn!.
͑
͑4͒ The number of acyclic orientations with exactly one source is
Tn 1,0͒ϭ nϪ1͒!.
͑
͑
͑5͒ The number of k-colorings, for any fixed k, is given by the Stirling polynomials so
Tn 1Ϫk,0͒ϭ Ϫ1͒nϪ1k kϪ1͒¯ kϪnϩ1͒.
͑
͑
͑
͑
͑6͒ The number of forests is
nϪ2
2,1͒ϳͱen
Tn
as n→ϱ.
͑
18
See for example Renyi17 or Denes.
´
Hence this gives a good picture of the sort of asymptotics one might expect.
It would be nice if there was a compact useful formula for the Tutte polynomial of the
complete graph as there is for the chromatic polynomial. Unfortunately this does not seem to be
the case and all that seems possible is to obtain a generating function expansion which is not that
useful. It was originally obtained by Tutte.19 Two different forms of this are in Refs. 20 and 21.
Welsh20 gives
n
͑xϪ1͒͑yϪ1͒
ϱ
ϱ
ͩ ͪ
j!
yϪ1͒nsnT x,y͒
sjy
2
͑
͑
n
1ϩ xϪ1͒
ϭ
.
͑17͒
͑
ͩ
ͪ
͚
͚
n!
nϭ1
jϭ0
Substituting (xϪ1)(yϪ1)nTn(x,y)ϭBn(Q,y) we get the following generating function for
the bad coloring polynomial or equivalently Z(Kn):
n
Q
ϱ
ϱ
ͩ ͪ
j!
snBn Q,y͒
sjy
2
͑
1ϩ
ϭ
.
ͩ
ͪ
͚
͚
n!
nϭ1
jϭ0
One way of obtaining this directly is the following.
Let
ϱ
Bn Q;s ,...,s ͒
͑
1
Q
un
͚
n!
nϭ0
be the generating function in which the coefficient of
m
m
sm1 1s2 ¯sQQu
n
2
is the number of ways of coloring Kn with Q colors ͕1, 2, ..., Q͖ where mi is the number of edges
with both end points colored i, for 1рiрQ.
Then clearly as
k
2
k
Q
2
1
n!
ͩ
ͪ
ͩ
ͪ
B K ;s ,...,s ͒ϭ
s1 ¯sQ
͑
͚
n
1
Q
k1!¯kQ!
k ϩ¯ϩk ϭn
1
Q
we conclude that
Downloaded 17 Apr 2013 to 198.91.37.2. This article is copyrighted as indicated in the abstract. Reuse of AIP content is subject to the terms at: http://jmp.aip.org/about/rights_and_permissions

J. Math. Phys., Vol. 41, No. 3, March 2000
The Potts model and the Tutte polynomial
1137
r
ͩ ͪ
ϱ
Q
ϱ
2
si
B K ;s ,...,s ͒
͑
n
1
Q
r
unϭ
u
.
ͩ
ͪ
͚
͟
͚
n!
r!
nϭ0
iϭ1
rϭ0
Now, this gives more information than we are asking for and putting
s1ϭs2ϭ¯ϭsQϭs
we get
n
Q
ϱ
ϱ
ͩ ͪ
2
B K ;Q,s͒
s
͑
n
unϭ
ur
.
ͩ
ͪ
͚
͚
n!
r!
nϭ0
rϭ0
One of the annoying features of the above-mentioned expansions is that they seem to be of
little help in attacking problems we wish to solve. As an example of this consider the evaluation
at xϭ2, yϭ1 which gives F(n) the number of forests in the complete graph. Direct substitution
in ͑17͒ does not seem to give us anything useful, in particular, we do not see how to get the
following result from ͑17͒.
Takacs22 gives the following exponential generating function for F(n):
ϱ
ϱ
F n͒
nnϪ2
͑
snϭexp
sn
.
ͫ
ͬ
͚
͚
n!
n!
nϭ1
nϭ1
He also gives the more useful
n
n
r
F n͒ϭ
͑
nnϪrHrϩ1 1͒,
͑
ͩ ͪ
͚
rϭ0
where Hn(x) is the nth Hermite polynomial defined by
͓n/2͔
Ϫ1͒jxnϪ2j
͑
Hn x͒ϭn!
.
͑
͚
2j j! nϪ2j͒!
͑
jϭ0
An extension of this by Stanley23 gives the number F(i,n) of forests with i edges on Kn as
having generating function
sitn
snϪ1 n
t
F i,n͒
͑
ϭexp nnϪ2
.
ͩ
ͪ
͚ ͚
n!
n!
nу0
i
16
´
We now turn to the recent work of Bollobas, Grimmett, and Janson on the asymptotics of
the random cluster model. Recall that if Z(n,p,Q) denotes the partition function of ZRC(Kn ;p,Q)
then this gives the Potts model on Kn by the substitution
pϭ1ϪeϪk
One of the main results ͑Theorem 2.616͒ is the following:
Theorem 3: If Qу1 and ␭Ͼ0, then
1
␭
log Z n, ,Q →␾ ␭,Q͒
͑
ͩ
ͪ
n
n
as n→ϱ, where the free energy ␾(␭,Q) is given by
Downloaded 17 Apr 2013 to 198.91.37.2. This article is copyrighted as indicated in the abstract. Reuse of AIP content is subject to the terms at: http://jmp.aip.org/about/rights_and_permissions

1138
J. Math. Phys., Vol. 41, No. 3, March 2000
D. J. A. Welsh and C. Merino
g ␪ ␭͒͒
QϪ1͒␭
2Q
͑ ͑
͑
␾ ␭,Q͒ϭ
͑
Ϫ
ϩlog Q
2Q
and where g(␪) is defined by
g ␪͒ϭϪ QϪ1͒ 2Ϫ␪͒log 1Ϫ␪͒Ϫ 2ϩ QϪ1͒␪ log 1ϩ QϪ1͒␪ .
͑
͑
͑
͑
͑
͑
͕
͖
͕
͖
The function ␪(␭)(ϭ␪(␭,Q)) is defined as
0
if ␭Ͻ␭ Q͒
͑
c
␪ ␭,Q͒ϭ
͑
ͭ
␪
if ␭у␭ Q͒,
͑
c
max
where
Q
if 0ϽQр2
QϪ1
QϪ2
␭ Q͒ϭ
͑
c
ͭ
2
log QϪ1͒ if QϾ2
͑
ͩ
ͪ
and ␪
is the largest root of the equation
max
1Ϫ␪
eϪ␭␪
ϭ
.
1ϩ QϪ1͒␪
͑
This explains the asymptotics in the region xу1, yу1 of the Tutte plane but note that it says
nothing about the antiferromagnetic part.
VII. THE COMPLEXITY OF THE TUTTE PLANE
We have seen that along different curves of the x,y plane, the Tutte polynomial evaluates
many diverse quantities. Since it is also the case that for particular curves and at particular points
the computational complexity of the evaluation can vary from being polynomial time computable
to being #P-hard a more detailed analysis of the complexity of evaluation is needed in order to
give a better understanding of what is and is not computationally feasible for these sort of prob-
lems. The main result of Jaeger, Vertigan, and Welsh24 is the following:
Theorem 4: The problem of evaluating the Tutte polynomial of a graph at a point (a,b) is
#P-hard except when (a,b) is on the special hyperbola
H ϵ xϪ1͒ yϪ1͒ϭ1
͑
͑
1
or when (a,b) is one of the special points ͑1, 1͒, ͑Ϫ1, Ϫ1͒, ͑0, Ϫ1͒, ͑Ϫ1, 0͒, (i,Ϫi), (Ϫi,i),
(j, j2) and (j2, j), where jϭe2␲i/3. In each of these exceptional cases the evaluation can be done
in polynomial time.
As far as the easy real points are concerned, with one exception, the explanation is straight-
forward. The hyperbola H1 is trivial, ͑1, 1͒ gives the number of spanning trees, ͑Ϫ1, 0͒ and ͑0,
Ϫ1͒ give the number of two-colorings and two flows respectively, and are easy evaluations of the
antiferromagnetic Ising. The point ͑Ϫ1, Ϫ1͒ is less well known but has been explained, see Sec.
V. It lies on the four-state Potts curve but as far as we are aware has no natural explanation there.
Finally the complex points (i,Ϫi)(Ϫi,i) lie on the Ising curve and the points (j, j2)(j2, j) lie
on the three-state Potts. Again there seems to be no natural interpretation to explain why their
evaluation is easy. The only reason why they appear in Theorem 4 is that they ‘‘turn up in the
calculations.’’
Downloaded 17 Apr 2013 to 198.91.37.2. This article is copyrighted as indicated in the abstract. Reuse of AIP content is subject to the terms at: http://jmp.aip.org/about/rights_and_permissions

J. Math. Phys., Vol. 41, No. 3, March 2000
The Potts model and the Tutte polynomial
1139
For planar graphs there is a significant difference. The technique developed using the Pfaffian
to solve the Ising problem for the plane square lattice by Kasteleyn25 can be extended to give a
polynomial time algorithm for the evaluation of the Tutte polynomial of any planar graph along
the special hyperbola
H ϵ xϪ1͒ yϪ1͒ϭ2.
͑
͑
2
However H3 cannot be easy for planar graphs since it contains the point ͑Ϫ2, 0͒ which counts the
number of three-colorings and since deciding whether a planar graph is three-colorable is NP-hard,
this must be at least NP-hard. However it does not seem easy to show that H4 is hard for planar
graphs. The decision-problem is after all trivial by the four-color theorem. The fact that it is
#P-hard is just part of the following extension of Theorem 4 due to Vertigan and Welsh.26
Theorem 5: The evaluation of the Tutte polynomial of bipartite planar graphs at a point (a,b)
is #P-hard except when
a,b͒෈H ഫH ഫ 1,1͒, Ϫ1,Ϫ1͒, j, j2͒, j2, j͒
͑
͑
͑
͑
͑
͕
͖
1
2
when it is computable in polynomial time.
It follows immediately from the fact that any graph can be represented as a totally unimodular
matrix that if a problem is hard ͑in any formal sense͒ for graphs then it will be at least as hard for
matrices.
VIII. APPROXIMATIONS
Since exact evaluation is provably hard, we turn to the possibility of obtaining good approxi-
mations or Monte Carlo estimates.
For positive numbers a and rу1, we say that a third quantity aˆ approximates a within ratio
r or is an r-approximation to a, if
r
Ϫ1aрaˆ рra.
͑18͒
In other words the ratio aˆ /a lies in rϪ1,r .
͓
͔
First consider what it would mean to be able to find a polynomial time algorithm which gave
an approximation within r to the number of three-colorings of a graph. We would clearly have a
polynomial time algorithm which would decide whether or not a graph is three-colorable. But this
is NP-hard. Thus no such algorithm can exist unless NPϭP.
The same argument can be applied to any function which counts objects whose existence is
NP-hard to decide. Hence
Proposition 6: Unless NPϭP there can be no polynomial time approximation to T(G;1
Ϫk,0) for integer kу3.
However this argument only applies to a few points of the Tutte plane and it seems a difficult
problem to decide on the existence of good approximations elsewhere.
We now consider a randomized approach to counting problems and make the following
definition.
An ⑀-␦-approximation scheme for a counting problem f is a Monte Carlo algorithm which on
˜
every input ͗x, ⑀, ␦͘, ⑀Ͼ0, ␦Ͼ0, outputs a number Y such that
˜
Pr 1Ϫ⑀͒f x͒рYр 1ϩ⑀͒f x͒ у1Ϫ␦.
͑
͑
͑
͑
͕
͖
Now let f be a function from input strings to the natural numbers. A randomized approxima-
tion scheme for f is a probabilistic algorithm that takes as an input a string x and a rational number
⑀, 0Ͻ⑀Ͻ1, and produces as output a random variable Y, such that Y approximates f(x) within
ratio 1ϩ⑀ with probability greater or equal 3/4.
In other words,
Downloaded 17 Apr 2013 to 198.91.37.2. This article is copyrighted as indicated in the abstract. Reuse of AIP content is subject to the terms at: http://jmp.aip.org/about/rights_and_permissions

1140
J. Math. Phys., Vol. 41, No. 3, March 2000
D. J. A. Welsh and C. Merino
1
Y
3
4
Pr
р
р1ϩ⑀ у
.
͑19͒
ͭ
ͮ
1ϩ⑀ f x͒
͑
*
A fully polynomial randomized approximation scheme ͑fpras͒ for a function f:͚ →N is a
randomized approximation scheme which runs in time which is a polynomial function of n and
Ϫ1
⑀
.
Suppose now we have such an approximation scheme and suppose further that it works in
polynomial time. Then we can boost the success probability up to 1Ϫ␦ for any desired ␦Ͼ0, by
using the following trick of Jerrum, Valiant, and Vazirani.27 This consists of running the algorithm
O(log ␦Ϫ1) times and taking the median of the results.
We make this precise as follows:
Proposition 7: If there exists a fpras for computing f then there exists an ⑀–␦ approximation
scheme for f which on input ͗x, ⑀, ␦͘ runs in time which is bounded by O(log␦Ϫ1)poly(x,⑀Ϫ1).
The existence of a fpras for a counting problem is a very strong result, it is the analog of a
randomized polynomial time ͑RP͒ algorithm for a decision problem and corresponds to the notion
of tractability. However we should also note
*
Proposition 8: If f:͚ →N is such that deciding if f is nonzero is NP-hard then there cannot
exist a fpras for f unless NP is equal to random polynomial time RP.
Hence we have immediately from the NP-hardness of k-coloring, for kу3, that:
Unless NPϭRP there cannot exist a fpras for evaluating T(G;Ϫk,0) for any integer kу2.
Recall now that along the hyperbola, HQ , for positive integer Q,T evaluates the partition
function of the Q-state Potts model.
In an important paper, Jerrum and Sinclair28 have shown that there exists a fpras for the
ferromagnetic Ising problem. Their result can be restated in our terminology as follows.
͑1͒ There exists a fpras for estimating T along the positive branch of the hyperbola H2 .
However it seems to be difficult to extend the argument to prove a similar result for the
Q-state Potts model with QϾ2 and this remains one of the outstanding open problems in this area.
A second result of Jerrum and Sinclair is the following:
͑2͒ There is no fpras for estimating the antiferromagnetic Ising partition function unless
NPϭRP.
In the context of its Tutte plane representation this can be restated as follows.
͑3͒ Unless NPϭRP, there is no fpras for estimating T along the curve
x,y͒: xϪ1͒ yϪ1͒ϭ2, 0ϽyϽ1 .
͑
͑
͑
͕
͖
The following extension of this result is proved in Welsh.29
Theorem 9: On the assumption that NPÞRP, the following statements are true.
͑a͒ Even in the planar case, there is no fully polynomial randomized approximation scheme
for T along the negative branch of the hyperbola H3 , that is for the antiferromagnetic three-state
Potts model.
͑b͒ For Qϭ2,4,5,..., there is no fully polynomial randomized approximation scheme for T
along the curves
HϪപ xϽ0 .
͕
͖
Q
It is worth emphasizing that the above-mentioned statements do not rule out the possibility of
there being a fpras at specific points along the negative hyperbolas. For example;
͑1͒ T can be evaluated exactly at ͑Ϫ1, 0͒ and ͑0, Ϫ1͒, which both lie on HϪ2 .
͑2͒ There is no inherent obstacle to there being a fpras for estimating the number of k-colorings of
a planar graph for any kу4.
Positive results: Mihail and Winkler30 have shown that there exists a fpras for counting the
number of ice configurations in a four-regular graph. This is equivalent to the statement:
Downloaded 17 Apr 2013 to 198.91.37.2. This article is copyrighted as indicated in the abstract. Reuse of AIP content is subject to the terms at: http://jmp.aip.org/about/rights_and_permissions

J. Math. Phys., Vol. 41, No. 3, March 2000
The Potts model and the Tutte polynomial
1141
There is a fpras for computing T at ͑0, Ϫ2͒ for four-regular graphs.
The reader will note that all the ‘‘negative results’’ are about evaluations of T in the region
outside the quadrant xу1, yу1. In Welsh1 it is conjectured that the following is true:
Conjecture 10: There exists a fpras for evaluating T at all points of the quadrant xу1, y
у1.
Some evidence in support of this is the following.
If we let G␣ be the collection of graphs Gϭ(V,E) such that each vertex has at least ␣
neighbors, then we call a class C of graphs dense if CʕG␣ for some fixed ␣Ͼ0.
Annan31 showed that:
͉V͉
Proposition 11: For any class of dense graphs, there is a fpras for evaluating T(G;x,1) for
positive integer x.
Extending this, Alon, Frieze, and Welsh32 show
Theorem 12: ͑a͒ There exists a fully polynomial randomized approximation scheme for evalu-
ating T(G;x,y) for all xу1, yу1, for any dense class of graphs.
͑b͒ For any class of strongly dense graphs, meaning G෈G␣ for ␣Ͼ 21, there is also such a
scheme for xϽ1, yу1.
Even more recently Karger33 has proved the existence of a similar scheme for the class of
graphs with no small edge cut set. This can be stated as follows.
c
c
For cϾ0 define the class G by G෈G if and only if its edge connectivity is at least
c
c log
͉
V(G)
͉
. A class of graphs is well connected if it is contained in G for some fixed c.
Theorem 13: For any fixed (x,y), yϾ1, there exists c, depending on (x,y), such that for any
c
class CʕG , there is a fpras for evaluating T(G;x,y).
Notice that though the properties of being well connected and dense are very similar neither
property implies the other.
Notice also that part ͑a͒ of Theorem 12 can be loosely reinterpreted as ͑a͒ There is a good
Monte Carlo scheme for estimating the partition function of the random cluster model on any class
of dense graphs.
Unfortunately there are several important classes of graphs, in particular lattices, which are
not dense.
IX. THE POTTS MODEL AND ERROR CORRECTING CODES
We now turn to a curious correspondence between the partition functions of the Q-states Potts
model whenever Q is a power of a prime and the weight enumerator polynomial of linear codes
over the finite field with Q elements. This correspondence is reasonably well known for the case
Qϭ2, the Ising model. It has been pointed out for example by Hoede34 and Rosengren and
Lindstrom.35 In Ref. 25 this correspondence was used to derive terms of the low temperature series
¨
expansion of the partition function Z of the three-dimensional cubic lattice.
For the purpose of this section take q to be any prime power and let C be a linear code over
the field GF(q).
A compact description of C is by a kϫn generator matrix G. The code words of C are all
linear combinations of rows of G. Now let Eϭ e ,...,e be the column vectors of G and take M
͕
͖
1
n
to be the matroid ͑E,r͒, where each subset A of columns has rank r(A) equal to the maximum
number of linearly independent columns in A as in Sec. II.
The weight of a code word is the number of nonzero entries. Given a code C, let Ai denote the
number of code words which have weight i. The weight enumerator of C is
A C;t͒ϭ
͑
A ti.
͑20͒
͚
i
Then we have the following theorem of Greene.36
Theorem 14: Let C be a linear code of dimension k and length n over the field GF(q). Let G
be a kϫn generator matrix of C and let M be the matroid on the set of columns. Then the weight
enumerator A(C;t) is given by
Downloaded 17 Apr 2013 to 198.91.37.2. This article is copyrighted as indicated in the abstract. Reuse of AIP content is subject to the terms at: http://jmp.aip.org/about/rights_and_permissions

1142
J. Math. Phys., Vol. 41, No. 3, March 2000
D. J. A. Welsh and C. Merino
1ϩ qϪ1͒t 1
͑
A C;t͒ϭ 1Ϫt͒ktnϪkT M;
,
.
͑21͒
͑
͑
ͩ
ͪ
1Ϫt
t
The proof of this is not that difficult and can be found for example in Ref. 37.
If we compare this with the expression ͑14͒ for the partition function ZPotts(G) we can rewrite
it as
1ϩ QϪ1͒eϪK
1
͑
͉
V
͉
͉E͉Ϫ͉V͉ϩ1͒
ZPotts G;Q,K͒ϭQ 1ϪeϪK
͒
Ϫ1eϪK͑
T G;
,
͑
͑
ͩ
ͪ
1ϪeϪK
eϪK
so that there is a direct translation via
Q→qϭp␣,
eϪK→parameter t.
Under this correspondence we get
Ϫ1
A C;t͒ϭQ
͑
Z
eϪKϭt͒.
͑
Potts
Now let us consider what this means in the context of a graphic matroid. Given any finite
graph it is easy to find a representation of it as a generator matrix of a linear code over any finite
field.
The edges of the graph correspond to the columns of the matrix and a set A of columns is
linearly independent if and only if the corresponding edges form a forest.
Example: Working with the field GF͑2͒, K4 minus one edge has a representation
The resulting code generated by this matrix has eight code words of length 5 and weight
enumerator 1ϩ2z2ϩ4z3ϩz4.
Now lets consider how this can be interpreted in general. Writing the weight enumerator as in
͑20͒, we see that we have another expansion for the Potts partition function namely,
͉E͉
ZPotts G;Q,K͒ϭQ
A eϪKi
.
i
͑
͚
iϭ0
Note however that this only works when Q is a prime power.
X. THE POTTS MODEL AND COUNTING IN RANDOM GRAPHS
Although the theory of random graphs is highly developed, less attention seems to have been
paid to counting problems. Here we give some results obtained in Welsh20 which give new
interpretations of the Tutte polynomial as the expected value of classical counting functions.
Given an arbitrary graph G and p෈ 0,1 we denote by Gp the random subgraph of G
͓
͔
obtained by deleting each edge of G independently with probability 1Ϫp.
This is a generalization of the standard random graph model Gn,p which corresponds to
(Kn)p .
Downloaded 17 Apr 2013 to 198.91.37.2. This article is copyrighted as indicated in the abstract. Reuse of AIP content is subject to the terms at: http://jmp.aip.org/about/rights_and_permissions

J. Math. Phys., Vol. 41, No. 3, March 2000
The Potts model and the Tutte polynomial
1143
First an easy result to illustrate the notation. If f(Gp) denotes the number of forests in Gp
then, for G and p fixed this is a random variable and has an expectation which we denote by
f(G ) .
͗
͘
p
Routine calculation gives that for any connected graph G,
1
͉
͉
f G ͒ ϭp V Ϫ1T G;1ϩ ,1 .
͑
͗
͘
ͩ
ͪ
p
p
Turning now to colorings, we have:
Theorem 15: For any connected graph G and 0Ͻpр1, the random subgraph Gp has chro-
matic polynomial whose expectation is given by
͉V͉Ϫ1
␹ G ;␭͒ ϭ Ϫp͒
␭T G;1Ϫ␭pϪ1,1Ϫp͒.
͑
͑
͑
͘
͗
p
For the flow polynomial there is a similar, but more complicated evaluation, namely
Theorem 16: For any graph G the flow polynomial F(Gp ;␭) has expectation given by
͑a͒ if p෈(0,12)ഫ( 12,1), then
␭p
r
͑G͒
F G ;␭͒ ϭpr͑G͒ qϪp͒
T G;qpϪ1,1ϩ
,
*
͑
͑
͗
͘
ͩ
ͪ
p
qϪp
where qϭ1Ϫp;
͑b͒ if pϭ 12, then
͉
E
͉
Ϫ
͉
V
͉
ϩk͑G͒
͉E͉
2Ϫ
.
F G ;␭͒ ϭ␭
͑
͗
͘
1/2
Notice that parametrized in terms of the Potts model these give interpretations in the antifer-
romagnetic region.
XI. THE LIMIT AS Q\0
Several authors ͑See Wu2͒ have considered the formal limiting behavior of the Q-state Potts
model as Q→0. This makes more sense in the context of the random cluster model which we
recall is defined for all QϾ0. Let us now consider this convergence in more detail.
Suppose in the random cluster model, p and Q both tend to zero with p/Q kept constant at 1.
Then easy calculations show that in this case
ZRC G;p,Q͒
͑
lim
ϭT G;2,1͒.
͑
pr͑E͒
In other words, from Sec. V, the limit is the number of forests of G.
There are various other cases to consider.
͑a͒ If Q→0 with p fixed then
1
lim ZRC G;p,Q͒ϭcT G;1,
,
͑
ͩ
ͪ
1Ϫp
Q→0
where c is a constant. In other words we are getting
͑1͒ the reliability probability, which we have already mentioned and is a much studied topic,
͑2͒ the chip-firing game ͑Abelian sandpile model͒,
as two different realizations of this limiting behavior. We consider the latter in some
detail in Sec. XI B.
͑b͒ For the other part of the hyperbola H0 , consisting of yϭ1, xу1, it is clear that if we let
Q→0 in such a way that Q/p is fixed at ␣Ͼ0, then in the random cluster model
Downloaded 17 Apr 2013 to 198.91.37.2. This article is copyrighted as indicated in the abstract. Reuse of AIP content is subject to the terms at: http://jmp.aip.org/about/rights_and_permissions

1144
J. Math. Phys., Vol. 41, No. 3, March 2000
D. J. A. Welsh and C. Merino
Qq
xϭ1ϩ
yϭ
→1ϩ␣,
→1
p
1
1Ϫp
and so
Ϫ
͉
E
͉
ϩr͑E͒
pϪr 1Ϫp͒
ZRC G;Q,p͒→T G;1ϩ␣,1͒.
͑
͑
͑
We have already mentioned the case ␣ϭ1 where the limit is the number of forests. More
generally we have the interesting specialization
␭rT G;1ϩ1/␭,1͒ϭi P G͒,␭͒,
͑
͑ ͑
where i is the Ehrhart polynomial of a particular family of zonotopes P(G) determined by a
graph G.
We now discuss in more detail these two separate problems areas.
A. The Ehrhart polynomial
Let Zn denote the n-dimensional integer lattice in Rn and let P be an n-dimensional lattice
polytope in Rn, that is a convex polytope whose vertices have integer coordinates. Consider the
function i(P;t) which when t is a positive integer counts the number of lattice points which lie
inside the dilated polytope tP. Ehrhart38 initiated the systematic study of this function by proving
that it was always a polynomial in t, and that in fact
nϪ1
i P,t͒ϭ␹ P͒ϩc tϩ¯ϩc
t
nϪ1
ϩvol P͒tn.
͑
͑
͑
1
Here c0ϭ␹(P) is the Euler characteristic of P and vol(P) is the volume of P.
Until recently the other coefficients of i(P,t) remained a mystery, even for simplices, see for
example Diaz and Robins.39
However, in the special case that P is a unimodular zonotope there is a nice interpretation of
these coefficients. First recall that if A is an rϫn matrix, written in the form Aϭ a ,...,a , then
͓
͔
1
n
it defines a zonotope Z(A) which consists of those points p of Rr which can be expressed in the
form
n
pϭ
␭ a , 0р␭iр1.
i i
͚
iϭ1
In other words, Z(A) is the Minkowski sum of the line segments 0,a ,1рiрn.
͓
͔
i
Z(A) is a convex polytope which, when A is a totally unimodular matrix, has all integer
vertices and in this case it is described as a unimodular zonotope. For these polytopes a result from
Stanley40 shows that
r
i Z A͒;t͒ϭ
͑ ͑
iktk,
͚
kϭ0
where ik is the number of subsets of columns of the matrix A which are linearly independent and
have cardinality k.
In other words, the Ehrhart polynomial i(Z(A);t) is the generating function of the number of
independent sets in the matroid M(A). But from ͑2.3͒ we know that for any matroid M, the
evaluation of T(M;x,y) along the line yϭ1 also gives this generating function. Hence, combining
these observations we have the result
Downloaded 17 Apr 2013 to 198.91.37.2. This article is copyrighted as indicated in the abstract. Reuse of AIP content is subject to the terms at: http://jmp.aip.org/about/rights_and_permissions

J. Math. Phys., Vol. 41, No. 3, March 2000
The Potts model and the Tutte polynomial
1145
Theorem 17: If M is a regular matroid and A is any totally unimodular representation of M
then the Ehrhart polynomial of the zonotope Z(A) is given by
1
i Z A͒;␭͒ϭ␭rT M;1ϩ ,1 ,
͑ ͑
ͩ
ͪ
␭
where r is the rank of M.
Another new interpretation of T follows from what is sometimes known as the Ehrhart–
Macdonald reciprocity law. This states that for any convex polytope P with integer vertices in Rn
and for any positive integer t, the function k(P;t) counting the number of lattice points lying
strictly inside tP is given by
k P;t͒ϭ Ϫ1͒ni P;Ϫt͒.
͑
͑
͑
This gives
Corollary 18: If A is an rϫn totally unimodular matrix of rank r then for any positive integer
␭ the number of lattice points of Rr lying strictly inside the zonotope ␭Z(A) is given by
1
k Z A͒;␭͒ϭ Ϫ␭͒rT M A͒;1Ϫ ,1 .
͑ ͑
͑
͑
ͩ
ͪ
␭
In particular we have the following new interpretations:
The number of lattice points strictly inside Z(A) is (Ϫ1)r(M)T(M;0,1).
B. Sandpiles
Self-organized criticality is a concept widely considered in various domains since Bak, Tang,
and Wiesenfeld41 introduced it ten years ago. One of the paradigms in this framework is the
Abelian sandpile model, introduced by Dhar.42
We start by recalling the definition of the general Abelian sandpile model on a set of N sites
labeled 1, 2, ..., N, that we referred to as the system. At each site the height of the sandpile is given
ជ
by an integer h . The set hϭ h is called the configuration of the system. For every site i, a
͕ ͖
i
i
threshold Hi is defined; configurations with hiϽHi are called stable. For every stable configura-
tion, the height hi increases in time at a constant rate, this is called the loading of the system. This
loading continues until at some site i, its height hi exceeds the threshold Hi , then the site i topples
and all the values hj, 1рjрN, are updated according to the rule:
hjϭhjϪ⌬ij for all j,
where ⌬ij is an integer matrix satisfying
͑22͒
⌬iiϾ0, ⌬ijр0, s ϭ
⌬ у0.
ij
͚
i
j
If after this redistribution some height exceeds its threshold we apply the toppling rule ͑22͒ and so
on, until we arrive at a stable configuration and the loading resumes. The sequence of topplings is
called an avalanche. We assume that an avalanche is ‘‘instantaneous,’’ and thus, no loading
occurs during an avalanche.
The value si is called the dissipation at site i. It may happen that an avalanche continues
without end. We can avoid this possibility by requiring that from every nondissipative site i, i.e.,
siϭ0, there exists a path to a dissipative site j, i.e., sjϾ0. In other words, there is a sequence
i0 ,...,in , with i0ϭi, inϭj, and ⌬i
kϽ0, for kϭ1,...,n. In this case we said that the system is
,i
kϪ1
weakly dissipative.43 From now on, we assume that the system is always weakly dissipative.
Downloaded 17 Apr 2013 to 198.91.37.2. This article is copyrighted as indicated in the abstract. Reuse of AIP content is subject to the terms at: http://jmp.aip.org/about/rights_and_permissions

1146
J. Math. Phys., Vol. 41, No. 3, March 2000
D. J. A. Welsh and C. Merino
When the matrix ⌬ij is symmetric and the loading of the system at site i equals the dissipation
at i, the Abelian sandpile model coincides with the chip-firing game on a graph.44 We now explain
this.
Every site of the Abelian sandpile model corresponds to a vertex in a graph G containing N
ϩ1 vertices, that is the number of vertices is one more than the number of sites in the system. We
label the vertices 0, 1, ..., N. The graph has multiple edges, and the number of edges between sites
N
jϭ1
i and j, i and j both nonzero, equals
edges.
͉
⌬
͉
. For all iÞ0, we connect site i to site 0 using
͉
͚
⌬
͉
ij
ij
Every vertex i, 1рiрN, has a number of chips ␪ that represents its height hi ͑when seen as
i
a site of the system͒ at every moment of time and vertex 0 has a negative number of chips given
N
by ͚iϭ1(Ϫhi). A toppling at site i corresponds to firing vertex i, that is, to redistribute some of the
chips at vertex i according to the following rule: At vertex j, the new number of chips is ␪
j
Ϫ⌬ij , for all j, that is, each neighbor k of i in G receives ͉⌬ ͉ chips and vertex i loses ⌬ii chips.
ik
The loading of the system is represented by the firing of the vertex 0, in this case the height of site
i ͑its number of chips in G͒ is increased by the number of edges from 0 to i. The vertex 0 may
͑must͒ fire only when no ordinary vertex can fire.
This process of firing vertices in the graph G is called a chip-firing game. The process is
infinite, although the number of firings corresponding to an avalanche in the system, that is, a
sequence of firings of the vertices 1, ..., N without firing the vertex 0, is finite. The number of
stable configurations is also finite, hence certain configurations are recurrent, that is, a configu-
ration is recurrent if there exists an avalanche which starts and ends with it. A configuration is
critical if it is recurrent and stable.
Using the chip-firing game it can be proved that this sandpile model has an important Abelian
property, namely the stable configuration of the system after an avalanche, and the number of
breaks at any site during an avalanche, do not depend on the order of breaks during the
avalanche.44 Even more, there is a close relation between the critical configurations of the system
and the Tutte polynomial of G. We now explain this more precisely.
ជ
The level of a configuration h is defined by
ជ
level h͒ϭ
h ϩdeg 0͒Ϫ͉E G͉͒.
͑ ͑
i
͑
͚
iÞ0
The theorem conjectured by Biggs45 and proved by Merino46 is the following
Theorem 19: If ci denotes the number of critical configurations of level i in a graph G with
special site 0, then
ϱ
Pq G;y͒ϭ
c yiϭT G;1,y͒.
͑
i
͑
͚
iϭ0
A first, nontrivial consequence of this is that it shows Pq(G;y) is independent of choice of the
vertex 0 in G.
Critical configurations possess some interesting mathematical properties: they form a finite
Abelian group whose order equals the number of spanning trees of the graph G. For the structure
of this group for planar graphs, n-wheels, and complete graphs, and in this case its relation with
parking functions see Ref. 47.
XII. RESISTOR NETWORKS
The problem of finding the effective resistance in a network of resistors was solved by
Kirchhoff ͑1847͒ but Fortuin and Kasteleyn5 showed that it also appears naturally as a limit of the
Potts partition function as Q→0.
Suppose we let Jij , the interaction energy between neighbor vertices i, j, be given by
Downloaded 17 Apr 2013 to 198.91.37.2. This article is copyrighted as indicated in the abstract. Reuse of AIP content is subject to the terms at: http://jmp.aip.org/about/rights_and_permissions

J. Math. Phys., Vol. 41, No. 3, March 2000
The Potts model and the Tutte polynomial
1147
JijϳϪkTrϪij 1
,
where rij is the resistance of the resistor connecting sites i and j.
Now we wish to find the effective resistance Rkl between two fixed sites k and l, where k and
l are joined in G. Then the result in Ref. 5 can be stated as in Ref. 2, namely
ץ
Rklϭ lim
ln ZRC G;Q,Q␣x ͒,
͑
ij
ץxkl
Q→0
where xijϭrϪij 1 for each edge (i, j)෈E(G) and ␣ is arbitrary in the open interval ͑0, 1͒.
As explained in Ref. 2 this is essentially obtained from a fairly well known interpretation of
the effective resistance in terms of a spanning tree polynomial which goes back to Kirchhoff. This
spanning tree polynomial which is denoted by S(G;xij) is multivariate and defined by
S G;x ͒ϭ
xij
,
͑
͚ ͚
͟
ij
ͩ
ͩ
ͪͪ
AʕE TʕG:A
͑i, j͒෈T
where the variables xij are indeterminates associated with each edge and the inner sum is over all
spanning trees T of the subgraph G:Aϭ(V(G),A).
Then the claim ͓͑Ref. 2͒, 4.26͔ is that for any ␣, 0Ͻ␣Ͻ1,
lim Q␣͑1ϪN͒Ϫ1ZRC G;Q,Q␣x ͒ϭS G;x ͒.
͑
͑
ij
ij
Q→0
Taking xijϭrϪij 1 gives the result of Kirchhoff.
Now let us reappraise this in terms of the Tutte polynomial. First of all, we should emphasize
that because it is a general result with variables rij and hence variable interaction strengths Jij , its
description cannot be exactly covered by the Tutte polynomial which is just two variable. How-
ever the basic ingredients are there. It is well known and easy to prove that in the case where all
resistances are constant, say equal to 1, then the effective resistance Re between two vertices of G
which are joined by an edge e is given by
T GЉ ;1,1͒
͑
e
Reϭ
.
T G;1,1͒
͑
Putting xijϭrϪ1 in S(G;xij) gives
͉
͉
͉
Ϫ͉V͉ϩ1
1
2 E
S G; ϭrϪnϩ1
T G
͑
͉
A;1,1͒ϭ
T G;1,1͒.
͑
ͩ ͪ
͚
͉
Ϫ1
r
r V
AʕE
Hence
T GЉ ;1,1͒
S GЉ ;rϪ1
͒
͑
͑
e
e
ϭr
.
T G;1,1͒
͑
S G;rϪ1
͒
͑
XIII. THE SQUARE LATTICE
For obvious reasons the two-dimensional lattice is a graph of fundamental importance in the
Potts model.
It is also the case that the square lattice is the fundamental separation point between the
classes of graphs of bounded tree width and unbounded tree width, in the sense of Robertson and
Seymour.48
Downloaded 17 Apr 2013 to 198.91.37.2. This article is copyrighted as indicated in the abstract. Reuse of AIP content is subject to the terms at: http://jmp.aip.org/about/rights_and_permissions

1148
J. Math. Phys., Vol. 41, No. 3, March 2000
D. J. A. Welsh and C. Merino
Thus, in a very technical sense, it can be regarded as the separation point between hard and
easy problems as all evaluations of the Tutte polynomial are known to be in polynomial time for
graphs of bounded tree width ͑see Andrzejak49 and Noble50͒. This was the motivation for the
Merino–Welsh paper51 which is the basis for the work of this section.
Here we review what is known about the Tutte polynomial on the square lattice.
The square lattice L is the set of ordered pairs (i, j)෈N2
͉
0рi, jрnϪ1 . There is an edge
͕
͖
n
between the vertices ͑i,j͒ and (i , j ) if ͉iϪi ͉ϩ͉jϪj ͉ϭ1.
Ј Ј Ј Ј
2
n
It is easy to show that as n→ϱ for any fixed ͑x,y͒, T(Ln ;x,y) is O(␪ ) for a suitable ␪
ϭ␪(x,y). We focus on the limit of the sequence
2
1/n
T L ,i, j͒͒
͑ ͑
͕
͖
n
for certain values of the integers i and j.
We note that we already know from the results of Grimmett52,53 and Biggs,54 that except in
certain special cases, these limits exist.
We first consider the trivial hyperbola H1 where
2
2
͑nϪ1͒
T L ;x,y͒ϭxn Ϫ1
y
.
͑
n
We next highlight the special hyperbola (xϪ1)(yϪ1)ϭ2. On the positive branch of this
hyperbola, which corresponds to the ferromagnetic version of the Ising model, convergence is to
the classical limit of the Onsager solution, see, e.g., Ref. 55.
Consider now ␹(Ln ;k), the number of k-colorings of the square lattice Ln . Clearly the
number of two-colorings of Ln is 2. Hence
lim ␹ L ;2͒͒ 2ϭ1.
1/n
͑ ͑
n
n→ϱ
For kϾ2 the problem becomes much harder and exact results are not known. An easy argu-
ment gives
kϪ2р ␹ L ;k͒͒ 2рkϪ1.
1/n
͑ ͑
n
For the rest of this section we assume nϾ2 to avoid trivialities. Let LTn be the graph obtained
from the square lattice Lnϩ1 by identifying the boundary vertices (i,0) and (i,n), for 0рiрn,
and the vertices (0,j) and (n, j), for 0рjрn, and deleting any parallel edge. This is the toroidal
square lattice. Let ␹(LTn ;k) be the number of k-colorings of LTn . It is known56 that for a fixed
2
2
integer kу3 the limits of the sequences (␹(LT ;k))1/n and (␹(L ;k))1/n are equal and we
͕
͖
͕
͖
n
n
call this limit ␹ˆ (k).
In a classical paper, Lieb57 showed that the number of ice configurations, see Sec. V, of LTn is
asymptotically (4/3)3/2. If we now assume LnT is self-dual, which is not strictly true because it is
nonplanar, it is generally accepted ͑Ref. 56, p. 56͒ that the result of Lieb implies that
␹ˆ 3͒ϭ 4/3͒3/2Ϸ1.539 600 718.
͑
͑
Biggs and Meredith in Ref. 58 obtained the estimate
␹ˆ k͒ϳ 1
2
kϪ3ϩͱk Ϫ2kϩ5͒.
͑
͑
2
Lower and upper bounds for ␹ˆ (k) were given by Biggs in Ref. 56. He used the transfer matrix
technique to obtain
k2Ϫ3kϩ3
kϪ1
1
2
2
kϪ2ϩͱk Ϫ4kϩ8͒.
͑
р␹ˆ k͒р
͑
Downloaded 17 Apr 2013 to 198.91.37.2. This article is copyrighted as indicated in the abstract. Reuse of AIP content is subject to the terms at: http://jmp.aip.org/about/rights_and_permissions

J. Math. Phys., Vol. 41, No. 3, March 2000
The Potts model and the Tutte polynomial
1149
In Ref. 59, Nagel used an induced subgraph expansion for the chromatic polynomial to obtain
the first terms of a power series that converges to ␹ˆ (k).
Kim and Enting60 gave a more accurate approximation of the same power series by combining
an expansion of ␹ˆ (k) due to de Neef and the transfer matrix technique.
Numerical values obtained by using this approximation give for example ␹ˆ (10)ϳ8.111... .
We use t(n) to denote the number of spanning trees of Ln . Let an be the number of one-
factors or perfect matchings of L2n . It is shown in Ref. 61 that
␲/2 ␲/2
ln an
n2
4
lim
n→ϱ
ϭ
ln 4 cos2 xϩ4 cos2 y͒dx dyϭcϷ1.166 243 696.
͑
2 ͵ ͵
␲
0
0
Now, let bn be the number of one-factors in the graph LЈn , which is obtained from the (2n
\
Ϫ1)ϫ(2nϪ1) square lattice by taking out one corner vertex, that is, LЈnϭL2nϪ1 (0,0). In Ref.
62, a bijection has been established between the one factors of LЈn and the spanning trees of Ln .
Since an /bnϳ1 as n→ϱ we get
2
lim t n͒͒ ϭecϷ3.209 912 556.
1/n
͑ ͑
n→ϱ
The number of spanning forests of Ln , which we denote by f(n), seems a much more elusive
quantity to approximate accurately. Now f(n) corresponds to T(Ln ;2,1) and the related points
T(Ln ;2,0) and T(Ln ;0,2) are the number of acyclic orientations of Ln ,␣(n), and the number of
acyclic orientations with ͑0,0͒ as the only source, ␣0(n), respectively. In Ref. 51 we show
2
7р lim ␣ n͒͒ р lim t n͒͒ 2Ϸ3.209 912 556,
1/n
1/n
͑
͑
0
͑ ͑
3
n→ϱ
n→ϱ
22
7
р lim ␣ n͒͒ 2р3.709 259 278...,
1/n
͑ ͑
n→ϱ
and
3.209 912 556р lim f n͒͒ 2р3.841 619 541... .
1/n
͑ ͑
n→ϱ
More recently, Calkin et al.63 have improved some of these upper bounds. By using the
transfer matrix method, they obtain
lim ␣ n͒͒ 2р3.563 221 504 771 6...,
1/n
͑ ͑
n→ϱ
lim f n͒͒ 2р3.746 981 401 399 4... .
1/n
͑ ͑
n→ϱ
Also, Merino and Noy64 have improved previous lower bounds by using generating function
techniques, their results are
13ϩͱ61
2
2
1/n
уͱ
lim ␣ n͒͒
n→ϱ
Ϸ3.225 697 573 851 8...,
͑ ͑
lim f n͒͒ 2у2ϩ&Ϸ3.414 213 562 373 1... .
1/n
͑ ͑
n→ϱ
Downloaded 17 Apr 2013 to 198.91.37.2. This article is copyrighted as indicated in the abstract. Reuse of AIP content is subject to the terms at: http://jmp.aip.org/about/rights_and_permissions

1150
J. Math. Phys., Vol. 41, No. 3, March 2000
D. J. A. Welsh and C. Merino
By using the transfer matrix method together with the Perron–Frobenius Theorem, they have also
obtained the following improvements:
lim ␣ n͒͒ 2у3.413 580 975 034 92...,
1/n
͑ ͑
n→ϱ
lim f n͒͒ 2у3.644 975 653 386 48... .
1/n
͑ ͑
n→ϱ
To sum up, the above-mentioned results give
2
7р lim ␣ n͒͒ р lim t n͒͒ 2Ϸ3.209 912 556,
1/n
1/n
͑
͑
0
͑ ͑
3
n→ϱ
n→ϱ
3.413 580 975 034 92...р lim ␣ n͒͒ 2р3.563 221 504 771 6...,
1/n
͑ ͑
n→ϱ
and
3.644 975 653 386 48...р lim f n͒͒ 2р3.746 981 401 399 4... .
1/n
͑ ͑
n→ϱ
Our objective is to find exact results for other evaluations T(Ln ;x,y) but this includes some
very difficult problems.
XIV. CONCLUSION
We hope that the above gives a reasonably coherent picture of the intimate relationship
between the Tutte polynomial and its physical interpretations associated with the Potts model.
One problem which has particularly engaged us is the question of whether there exists a good
Monte Carlo scheme for the ferromagnetic Potts or random cluster model. A recent attack on this
problem in Ref. 65 works as follows.
For any graph G, the win polytope WG is the convex polytope defined by
x рe U͒, UʕV, xiу0,
͑
͚
i
i෈U
where e(U) is the number of edges incident with U.
It has the property that its bounding base face is combinatorially equivalent to Z(A) where A
is any totally unimodular representation of the graph G as in Sec. XI A. Now carry out simple
random walk Xt in a slightly dilated version of WG , call it WЈG . Associate with each lattice point
a box of equal volume, ensuring that the boxes are disjoint but otherwise as large as possible. Now
let t be large enough, say tϭT so that the stopping point XT is almost uniform in WЈG , and map
XT to the lattice point associated with the box containing it. Accept the output as an almost
uniform point of WG if it lies inside it. Repeat N times, where N is large enough to ensure we have
a good estimate of the number of lattice points inside WG . Ideally this process would work
successfully enough to enable us also to get a good estimate of the number of lattice points in the
bounding face and hence in Z(A).
Curiously, and somewhat depressingly, in order for the method to work in polynomial time we
need exactly the same density condition on the underlying graph as did Annan.31 This suggests
that it might be more profitable to look for a mathematical reason why good approximation
schemes should not exist for Z(G;p,Q) for general p and Q.
Accordingly, problems which seem to us particularly interesting are the following:
͑a͒ Settle the Conjecture 10 that in the ferromagnetic region xу1, yу1 there is a good Monte
Carlo approximation for T(x,y).
Downloaded 17 Apr 2013 to 198.91.37.2. This article is copyrighted as indicated in the abstract. Reuse of AIP content is subject to the terms at: http://jmp.aip.org/about/rights_and_permissions

J. Math. Phys., Vol. 41, No. 3, March 2000
The Potts model and the Tutte polynomial
1151
͑b͒ Decide the question of whether the number of acyclic orientations has a good approximation.
͑c͒ Clarify, or at least explain more convincingly than the reasons given in Ref. 65 why it is so
hard to approximate the number of forests.
͑d͒ Understand better the region of the Tutte plane where the random cluster model is not
positively correlated.
ACKNOWLEDGMENTS
D.J.A. Welsh is supported in part by Esprit Working Group No. 21726, ‘‘RAND2.’’ C.M. is
supported by a grant from D.G.A.P.A.
1 D. J. A. Welsh, Complexity: Knots, Colourings and Counting, in London Mathematical Society Lecture Note Series, Vol.
186 ͑Cambridge University Press, Cambridge, 1993͒.
2 F. Wu, ‘‘The Potts model,’’ Rev. Mod. Phys. 54, 235–268 ͑1982͒.
3 J. G. Oxley, Matroid Theory ͑Oxford University Press, Oxford, 1992͒.
4 J. G. Oxley and D. J. A. Welsh, ‘‘The Tutte polynomial and percolation,’’ Graph Theory and Related Topics, edited by
J. A. Bondy and U.S.R. Murty ͑Academic, London, 1979͒, pp. 329–339.
5 C. M. Fortuin and P. W. Kasteleyn, ‘‘On the random cluster model. I. Introduction and relation to other models,’’
Physica ͑Amsterdam͒ 57, 536–564 ͑1972͒.
6 G. R. Grimmett, Precolation ͑Springer, Berlin, 1989͒.
7
´
´
´
G. R. Grimmett, Precolation and Disordered Systems, Ecole dEtee de probabilites de Saint Flour XXXVI–1996, edited
by P. Bernard ͓Lect. Notes Math. 1665, 153–300 ͑1997͔͒.
8 R. G. Edwards and A. D. Sokal, ‘‘Generalization of the Fortuin–Kasteleyn–Swendesen–Wang representation and Monte
Carlo algorithms,’’ Phys. Rev. D 38, 2009–2012 ͑1988͒.
9 R. H. Swendsen and J.-S. Wang, ‘‘Nonuniversal critical dynamics in Monte Carlo simulations,’’ Phys. Rev. Lett. 58,
86–88 ͑1987͒.
10 R. P. Stanley, ‘‘Acyclic orientations of graphs,’’ Discrete Math. 5, 171–178 ͑1973͒.
11 T. Zaslavsky, ‘‘Facing up to arrangements: Face count formulas for partitions of space by hyperplanes,’’ Memoirs of
American Mathematical Society 154 ͑1975͒.
12 R. C. Read and P. Rosenstiehl, ‘‘On the principal edge tripartition of a graph,’’ Ann. Discrete Math. 3, 195–226 ͑1978͒.
13 M. B. Thistlethwaite, ‘‘A spanning tree expansion of the Jones polynomial,’’ Topology 26, 297–309 ͑1987͒.
14 T. H. Brylawski and J. G. Oxley, The Tutte Polynomial and its Applications Matroid Applications, edited by N. White
͑Cambridge University Press, Cambridge, 1992͒, pp. 123–225.
15 H. Kesten and R. H. Schonmann, ‘‘Behavior in large dimensions of the Potts and Heisenberg models,’’ Rev. Math. Phys.
1, 147–182 ͑1989͒.
16
´
B. Bollobas, G. Grimmett, and S. Janson, ‘‘The random-cluster model on the complete graph,’’ Probab. Theory Related
Fields 104, 283–317 ͑1996͒.
17
18
´
A. Renyi, ‘‘Some remarks on the theory of trees,’’ Pub. Math. Inst. Hungarian Acad. Sci. 4, 73–85 ͑1959͒.
´
J. Denes, ‘‘The representation of a permutation as the product of a minimal number of transpositions, and its connection
with the theory of graphs,’’ Publ. Math. Inst. Hungarian Acad. Sci. 4, 63–71 ͑1959͒.
19 W. T. Tutte, ‘‘On dichromatic polynomials,’’ J. Comb. Theory, Sec. A 2, 301–320 ͑1967͒.
20 D. J. A. Welsh, ‘‘Counting, colourings and flows in random graphs,’’ Bolyai Society Mathematical Studies 2, 491–506
͑1996͒.
21 I. M. Gessel and B. E. Sagan, ‘‘The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions,’’
Electron. J. Combin. 3, 1–36 ͑1996͒.
22 L. Takacs, ‘‘On the number of distinct forests,’’ SIAM J. Discrete Math. 3, 574–581 ͑1990͒.
23 R. P. Stanley, A Zonotope Associated with Graphical Degree Sequences, DIMACS Series in Discrete Mathematics and
Theoretical Computer Science, Vol. 4, 555-570 ͑1991͒.
24 F. Jaeger, D. L. Vertigan, and D. J. A. Welsh, ‘‘On the computational complexity of the Jones and Tutte polynomials,’’
Math. Proc. Cambridge Philos. Soc. 108, 35–53 ͑1990͒.
25 P. W. Kasteleyn, ‘‘The statistics of dimers on a lattice,’’ Physica ͑Amsterdam͒ 27, 1209–1225 ͑1961͒.
26 D. L. Vertigan and D. J. A. Welsh, ‘‘The computational complexity of the Tutte plane: The bipartite case,’’ Comb.
Probab. Comput. 1, 181–187 ͑1992͒.
27 M. R. Jerrum, L. G. Valiant, and V. V. Vazirani, ‘‘Random generation of combinatorial structures from a uniform
distribution,’’ Theor. Comput. Sci. 43, 169–188 ͑1986͒.
28 M. R. Jerrum and A. Sinclair, ‘‘Polynomial-time approximation algorithms for the Ising model,’’ SIAM J. Comput. 22,
1087–1116 ͑1993͒.
29 D. J. A. Welsh, ‘‘Randomised approximation in the Tutte plane,’’ Comb. Probab. Comput. 3, 137–143 ͑1993͒.
30 M. Mihail and P. Winkler, ‘‘On the number of Eulerian orientations of a graph,’’ Algorithmica 16, 402–414 ͑1996͒.
31 J. D. Annan, ‘‘A randomized approximation algorithm for counting the number of forests in dense graphs,’’ Comb.
Probab. Comput. 3, 273–283 ͑1994͒.
32 N. Alon, A. M. Frieze, and D. J. A. Welsh, ‘‘Polynomial time randomized approximation schemes for Tutte–
Grothendieck invariants: The dense case,’’ Random Struct. Algorithms 6, 459–478 ͑1995͒.
33 D. R. Karger, ‘‘A randomized fully polynomial time approximation scheme for the all terminal network reliability
problem,’’ in Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, 1995 ͑unpub-
lished͒, pp. 328–337.
Downloaded 17 Apr 2013 to 198.91.37.2. This article is copyrighted as indicated in the abstract. Reuse of AIP content is subject to the terms at: http://jmp.aip.org/about/rights_and_permissions

1152
J. Math. Phys., Vol. 41, No. 3, March 2000
D. J. A. Welsh and C. Merino
34 C. Hoede, ‘‘The Ising model and linear codes,’’ Congr. Numer. 33, 81–108 ͑1981͒.
35
¨
A. Rosengren and B. Lindstrom, ‘‘A combinatorial series expansion for the Ising model,’’ Eur. J. Combin. 8, 317–323
͑1987͒.
36 C. Greene, ‘‘Weight enumeration and the geometry of linear codes,’’ Stud. Appl. Math. 55, 119–128 ͑1976͒.
37 D. J. A. Welsh, Matroid Theory ͑Academic, New York, 1976͒.
38
`
´
´
E. Ehrhart, ‘‘Sur un probleme de geometrie diophantienne lineaire I, II,’’ J. Reine Angew. Math. 226, 1–29 ͑1967͒; 227,
25–49 ͑1967͒; correction 231, 220 ͑1968͒.
39 R. Diaz and S. Robins, ‘‘The Ehrhart, polynomial of a lattice n-simplex,’’ Electron. Res. Announc. Am. Math. Soc. 2,
1–6 ͑1996͒.
40 R. P. Stanley, ‘‘Decompositions of rational convex polytopes,’’ Ann. Discrete Math. 6, 333–342 ͑1980͒.
41 P. Bak, C. Tang, and K. Wiesenfeld, ‘‘Self-organized criticality,’’ Phys. Rev. A 38, 364–374 ͑1988͒.
42 D. Dhar, ‘‘Self-organized critical state of sandpile automaton models,’’ Phys. Rev. Lett. 64, 1613–1616 ͑1990͒.
43 A. Gabrielov, ‘‘Abelian avalanches and the Tutte polynomials,’’ Physica A 195, 253–274 ͑1993͒.
44
¨
´
A. Bjorner, L. Lovasz, and P. Shor, ‘‘Chip-firing games on graphs,’’ Eu. J. Combin. 12, 283–291 ͑1991͒.
45 N. Biggs, ‘‘The Tutte polynomial as a growth function’’ ͑unpublished͒.
46 C. Merino, ‘‘Chip-firing and the Tutte polynomial,’’ Ann. Comb. 1, 253–259 ͑1997͒.
47 R. Cori and D. Rossin, ‘‘On the sandpile group of a graph’’ ͑unpublished͒.
48 N. Robertson and P. D. Seymour, ‘‘Graph Minors. II. Algorithmic aspects of tree-width,’’ J. Algorithm 7, 309–322
͑1986͒.
49 A. Andrzejak, ‘‘An algorithm for the Tutte polynomials of graphs of bounded tree width,’’ Discrete Math. 190, 39–54
͑1998͒.
50 S. Noble, ‘‘Evaluating the Tutte polynomial for graphs of bounded tree-width,’’ Comb. Probab. Comput. 7, 307–322
͑1998͒.
51 C. Merino and D. J. A. Welsh, ‘‘Forests, colorings and acyclic orientations of the square lattice,’’ Ann. Comb. 3,
417–429 ͑1999͒.
52 G. R. Grimmett, ‘‘Multidimensional lattices and their partition function,’’ Q. J. Math. 29, 141–157 ͑1978͒.
53 G. R. Grimmett, ‘‘The rank polynomials of large random lattices,’’ J. London Math. Soc. 18, 567–575 ͑1978͒.
54
´
N. L. Bıggs, ‘‘Chromatic and thermodynamic limits,’’ J. Phys. A 8, L110–112 ͑1975͒.
55 C. J. Thompson, Mathematical Statistical Mechanics ͑Princeton University Press, Princeton, NJ, 1979͒, pp. 131–135.
56 N. L. Biggs, ‘‘Colouring square lattice graphs,’’ Bull. London Math. Soc. 9, 54–56 ͑1977͒.
57 E. Lieb, ‘‘The residual entropy of square ice,’’ Phys. Rev. 162, 162–172 ͑1967͒.
58 N. L. Biggs and G. H. J. Meredith, ‘‘Approximations for chromatic polynomials,’’ J. Comb. Theory, Ser. B 20, 5–19
͑1976͒.
59 J. F. Nagle, ‘‘A new sugraph expansion for obtaining coloring polynomials for graphs,’’ J. Comb. Theory, Ser. B 10,
42–59 ͑1971͒.
60 D. Kim and I. G. Enting, ‘‘The limit of chromatic polynomials,’’ J. Comb. Theory, Ser. B 26, 327–336 ͑1979͒.
61
´
L. Lovasz, Combinatorial Problems and Exercises ͑North-Holland, Amsterdam, 1979͒, pp. 238–243.
62 H. N. V. Temperley, Combinatorics, in London Mathematical Society, Lecture Note Series Vol. 13 ͑Cambridge Uni-
versity Press, Cambridge 1974͒, pp. 202–204.
63 N. J. Calkin, C. Merino, S. Noble, and D. J. A. Welsh ͑private communication͒.
64 C. Merino and M. Noy ͑private communication͒.
65 E. Bartels, J. Mount, and D. J. A. Welsh, ‘‘The win polytope of a graph,’’ Ann. Comb. 1, 1–15 ͑1997͒.
Downloaded 17 Apr 2013 to 198.91.37.2. This article is copyrighted as indicated in the abstract. Reuse of AIP content is subject to the terms at: http://jmp.aip.org/about/rights_and_permissions