The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content

DAN

Seminar

The ferromagnetic Potts model: phase transition, gadgets and computational complexity

Jerrum, M (Queen Mary, London)
Thursday 21 April 2011, 14:00-15:00

Seminar Room 2, Newton Institute Gatehouse

Abstract

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.

Back to top ∧