Abstract: An instance of the
Potts model is defined by a graph of interactions and a number, q, of different ``spins''. A configuration in 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 q≠2 have been unsuccessful. At the
same time, no convincing evidence has been presented to indicate that such an
extension is impossible. An interesting
feature of the random cluster model when q>2 is that it exhibits a
first-order phase transition, while for 1≤q≤2 only a second-order phase transition
is apparent. The idea I want to convey
in this talk is that this first-order phase transition can be exploited in
order to encode apparently hard computational problems within the model. This provides the first evidence that the
partition function of the ferromagnetic Potts model may be hard to compute when
q>2.
This
is joint work with Leslie Ann Goldberg, University of Liverpool.