Spin Systems on Graphs, Critical Percolation and Scaling Limits

图上的自旋系统、临界渗透和缩放限制

• 批准号: 0104073
• 负责人: Yuval Peres
• 金额: $ 53.37万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-08-01 至 2007-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0104073&HistoricalAwards=false
• 关键词: Spin; Systems; Graphs; Critical; Percolation

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.

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