The ferromagnetic Potts model: phase transition, gadgets and computational complexity
Seminar Room 2, Newton Institute Gatehouse
An instance of the Potts model is defined by a graph of interactions and a number q
of different "spins". A configuration is this model is an assignment of spins to vertices.
Each configuration has a weight, which in the ferromagnetic case is greater when more
pairs of adjacent spins are alike. The classical Ising model is the special case of q=2
spins. We consider the problem of computing an approximation to the partition function,
i.e., weighted sum of configurations, of an instance of the Potts model.
Through the random cluster formulation it is possible to make sense
of the partition function also for non-integer q. Yet another equivalent formulation
is as the Tutte polynomial in the positive quadrant.
About twenty years ago, Jerrum and Sinclair gave an efficient (i.e., polynomial-time)
algorithm for approximating the partition function of a ferromagnetic Ising system.
Attempts to extend this result to q2 have been unsuccessful.
At the same time, no convincing evidence has been presented to indicate that
such an extension is impossible. In this talk, I sketch a recent result to the effect that,
for q>2, approximating the partition function of the ferromagnetic Potts model is hard
for a certain complexity class, which contains a large number of other approximation
problems for which no efficient approximation algorithm is known.
The reduction used to establish this result
exploits a first-order phase transition, already known to exist when q>2,
to construct a bi-stable combinatorial "gadget". Along the way, a hypergraph
version of the Tutte polynomial arises quite naturally.
This is joint work with Leslie Ann Goldberg, University of Liverpool.