| EPSRC Reference: |
EP/G066604/1 |
| Title: |
Approximation and mixing times in the ferromagnetic Potts model |
| Principal Investigator: |
Bordewich, Professor MJR |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| 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 non-equilibrium particle systems. In computer science, the Potts model is a test-bed 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 non-academic 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: |
|