Approximation and mixing times in the ferromagnetic Potts model

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

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.