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

Add to your list(s) Download to your calendar using vCal

• Jerrum, M (Queen Mary, London)
• Thursday 21 April 2011, 14:00-15:00
• Seminar Room 2, Newton Institute Gatehouse.

If you have a question about this talk, please contact Mustapha Amrani.

Discrete Analysis

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.

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 2, Newton Institute Gatehouse
• bld31

Note that ex-directory lists are not shown.