Spin Systems on Graphs, Critical Percolation and Scaling Limits

首席研究员将研究概率论中关于一般图和网络上随机过程的几个问题，特别是某些具有自然吉布斯测度作为平稳分布的马尔可夫过程（Glauber动力学）。研究者和他的合作者已经证明，对于树木上的伊辛模型（以及其他“双曲”图），在任何温度下，格劳伯动力学的混合时间是体积的多项式。此外，在有限规则树上，快速混合的临界温度低于相应无限树上吉布斯态唯一性的临界温度。研究者打算精确地研究图形几何的哪些方面（如光谱、Cheeger常数）与格劳伯动力学的混合速率最相关。“硬”组合问题的现代近似方案（例如，计算图中的匹配）使用与Glauber动力学相关的过程，因此对这些动力学的新见解将对随机近似算法产生影响。几十年来，统计物理学一直在研究相互作用粒子的大型网络，作为磁性、冻结和其他物理过程的模型。在这些模型中，每个粒子只与它的近邻相互作用，但从这种局部相互作用中，可以出现全局结构。这些系统随时间的演变被称为“格劳伯动力学”。在过去的二十年中，这些动态已被用于图像分析，近似计数算法和通信网络。虽然大多数可用的数学结果和物理预测仅限于相当特殊的网络（粒子排列在规则的晶格中），但它们已经激发了潜在网络具有完全不同结构的应用。研究者打算分析各种网络上的Glauber动力学，重点关注网络几何形状对动力学的影响。他正在与几位计算机科学家合作研究格劳伯动力学的算法方面。

The Principal Investigator will study several problems in Probability Theory concerning random processes on general graphs and networks, in particular certain Markov processes (Glauber dynamics) that have natural Gibbs measures as stationary distributions. The investigator and his collaborators have shown that for the Ising model on trees, (and on other "hyperbolic" graphs), the mixing time for Glauber dynamics is polynomial in the volume, at any temperature. Moreover, on a finite regular tree, the critical temperature for rapid mixing is lower than the critical temperature for uniqueness of Gibbs states on the corresponding infinite tree. The investigator intends to study precisely which aspects of the geometry of a graph (e.g. spectra, Cheeger constants) are most relevant to the mixing rate of Glauber dynamics. Modern approximation schemes for "hard" combinatorial problems (e.g., counting matchings in a graph) use processes related to Glauber dynamics, so new insights on these dynamics will have an impact on randomized approximation algorithms. Large networks of interacting particles have been studied for decades in statistical physics, as models of magnetism, freezing, and other physical processes. In these models, each particle interacts only with its immediate neighbors, yet from this local interaction, global structure can emerge. The evolution of these systems over time is called "Glauber dynamics". In the last twenty years, these dynamics have been used in image analysis, approximate counting algorithms, and communication networks. While most of the mathematical results and physical predictions available are restricted to quite special networks (where the particles are arranged in a regular lattice), they have motivated applications where the underlying network has completely different structure. The investigator intends to analyze Glauber dynamics on a variety of networks, with attention focussed on the effect of the network geometry on the dynamics. He is collaborating with several computer scientists on the algorithmic aspects of Glauber dynamics.