EPSRC Reference: 
EP/G066604/1 
Title: 
Approximation and mixing times in the ferromagnetic Potts model 
Principal Investigator: 
Bordewich, Professor MJR 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Engineering and Computing Sciences 
Organisation: 
Durham, University of 
Scheme: 
First Grant Scheme 
Starts: 
11 January 2010 
Ends: 
01 April 2013 
Value (£): 
250,380

EPSRC Research Topic Classifications: 
Complexity Science 
Fundamentals of Computing 
Logic & Combinatorics 
Magnetism/Magnetic Phenomena 
Statistics & Appl. Probability 


EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 
Panel Date  Panel Name  Outcome 
24 Apr 2009

ICT Prioritisation Panel (April 09)

Announced


Summary on Grant Application Form 
The Potts model was introduced in 1952 as a model of magnetism. The Potts model has been extensively studied not only in statistical physics, but also in computer science, mathematics and further afield. In physics the main interest is in studying phase transitions and modelling the evolution of nonequilibrium particle systems. In computer science, the Potts model is a testbed for approximation algorithms and techniques. It has also been heavily studied in the areas of discrete mathematics and graph theory, through an equivalence to the Tutte polynomial of a graph, and thereby links to the chromatic polynomial and many other graph invariants. The Potts model and its extensions have also appeared many times in the social sciences, for example in modelling financial markets and modelling voter interaction in social networks.In simple terms, a magnet is regarded as a large number of atoms arranged in a grid. These atoms oscillate randomly and are more likely to align themselves with their immediate neighbours than to orientate themselves differently. Under some circumstances all the atoms quickly become aligned uniformly. Under other circumstances a mixed state, in which blocks of atoms are orientated differently, persists for much longer. We are interested in exactly what aspects of the circumstances are key to determining which behaviour occurs. This project is concerned with understanding the speed of convergence of alignment to a steady state, and with computing the probability of a given configuration arising. The latter problem is hard, in a rigorous sense, and so the focus of effort is on approximation methods. We will develop approximation algorithms for this problem and study when approximations are or are not possible under standard complexity theoretic assumptions.

Key Findings 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Potential use in nonacademic contexts 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Impacts 
Description 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk 
Summary 

Date Materialised 


Sectors submitted by the Researcher 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Project URL: 

Further Information: 

Organisation Website: 
