14:15
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.