Spin Systems on Graphs, Critical Percolation and Scaling Limits

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

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.