权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Approximation and mixing times in the ferromagnetic Potts model

铁磁 Potts 模型中的近似和混合时间

基本信息

批准号：
EP/G066604/1
负责人：
Magnus Bordewich
金额：
$ 31.9万
依托单位：
Durham University
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2010
资助国家：
英国
起止时间：
2010 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FG066604%2F1
关键词：
Approximation mixing times ferromagnetic Potts

项目摘要

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.

波茨模型是1952年作为磁性模型引入的。波茨模型不仅在统计物理学中得到了广泛的研究，而且在计算机科学、数学和其他领域也得到了广泛的研究。在物理学中，主要的兴趣是研究相变和模拟非平衡粒子系统的演化。在计算机科学中，波茨模型是近似算法和技术的试验台。它也在离散数学和图论领域得到了大量的研究，通过等价于图的Tutte多项式，从而与色多项式和许多其他图不变量联系起来。波茨模型及其扩展也多次出现在社会科学领域，例如金融市场建模和社会网络中选民互动建模。简单地说，磁铁被看作是排列在网格中的大量原子。这些原子随机振荡，更有可能与它们的近邻排列在一起，而不是以不同的方向排列。在某些情况下，所有的原子很快就会均匀排列。在其他情况下，原子块取向不同的混合状态会持续更长时间。我们感兴趣的是环境的哪些方面是决定哪种行为发生的关键。这个项目关注的是了解对准收敛到稳定状态的速度，以及计算给定构型出现的概率。从严格意义上说，后一个问题很难，因此重点放在近似方法上。我们将为这个问题开发近似算法，并研究在标准复杂性理论假设下何时可能或不可能近似。