We study the problem of approximating the partition function of the ferromagnetic Ising model in graphs and hypergraphs. Our first result is a deterministic approximation scheme (an FPTAS) for the partition function in bounded degree graphs that is valid over the entire range of parameters &#x03B2; (the interaction) and &#x03BB; (the external field), except for the case |&#x03BB;|=1 (the zero-field case). A randomized algorithm (FPRAS) for all graphs, and all &#x03B2;,&#x03BB; has long been known. Unlike most other deterministic approximation algorithms for problems in statistical physics and counting, our algorithm does not rely on the decay of correlations property. Rather, we exploit and extend machinery developed recently by Barvinok, and Patel and Regts, based on the location of the complex zeros of the partition function, which can be seen as an algorithmic realization of the classical Lee-Yang approach to phase transitions. Our approach extends to the more general setting of the Ising model on hypergraphs of bounded degree and edge size, where no previous algorithms (even randomized) were known for a wide range of parameters. In order to achieve this extension, we establish a tight version of the Lee-Yang theorem for the Ising model on hypergraphs, improving a classical result of Suzuki and Fisher.
Much detailed work has been done on MCMC for Ising spin configurations for several important classes of graphs, including two-dimensional lattices (e.g., @cite_44 @cite_28 @cite_11 ), random graphs and graphs of bounded degree (e.g., @cite_26 ), the complete graph (e.g., @cite_1 ) and trees (e.g., @cite_31 @cite_17 ); we do not attempt to give a comprehensive summary of this line of work here.
@cite_26 @cite_28 @cite_1 @cite_17 @cite_44 @cite_31 @cite_11
2090216341 2963496965 1965879843 2011373957 2135481845 2079416076
We establish tight results for rapid mixing of Gibbs samplers for the Ferromagnetic Ising model on general graphs. We show that if (d−1) tanh β < 1, then there exists a constant C such that the discrete time mixing time of Gibbs samplers for the ferromagnetic Ising model on any graph of n vertices and maximal degree d, where all interactions are bounded by β, and arbitrary external fields are bounded by Cnlogn. Moreover, the spectral gap is uniformly bounded away from 0 for all such graphs, as well as for infinite graphs of maximal degree d. We further show that when dtanh β < 1, with high probability over the Erdős–Renyi random graph G(n,d n), it holds that the mixing time of Gibbs samplers is n1+Θ(1 loglogn). Both results are tight, as it is known that the mixing time for random regular and Erdős–Renyi random graphs is, with high probability, exponential in n when (d−1) tanh β> 1, and dtanh β>1, respectively. To our knowledge our results give the first tight sufficient conditions for rapid mixing of spin systems on general graphs. Moreover, our results are the first rigorous results establishing exact thresholds for dynamics on random graphs in terms of spatial thresholds on trees. Introduction Statement of the results Mixing time preliminaries Outline of the proof of Theorem 2.1 Random graph estimates Supercritical case Subcritical case Critical case Fast mixing of the Swendsen-Wang process on trees Acknowledgements Bibliography We give the first comprehensive analysis of the effect of boundary conditions on the mixing time of the Glauber dynamics in the so-called Bethe approximation. Specifically, we show that the spectral gap and the log-Sobolev constant of the Glauber dynamics for the Ising model on an n-vertex regular tree with (+)-boundary are bounded below by a constant independent of n at all temperatures and all external fields. This implies that the mixing time is O(logn) (in contrast to the free boundary case, where it is not bounded by any fixed polynomial at low temperatures). In addition, our methods yield simpler proofs and stronger results for the spectral gap and log-Sobolev constant in the regime where the mixing time is insensitive to the boundary condition. Our techniques also apply to a much wider class of models, including those with hard-core constraints like the antiferromagnetic Potts model at zero temperature (proper colorings) and the hard–core lattice gas (independent sets). Various finite volume mixing conditions in classical statistical mechanics are reviewed and critically analyzed. In particular somefinite size conditions are discussed, together with their implications for the Gibbs measures and for the approach to equilibrium of Glauber dynamics inarbitrarily large volumes. It is shown that Dobrushin-Shlosman's theory ofcomplete analyticity and its dynamical counterpart due to Stroock and Zegarlinski, cannot be applied, in general, to the whole one phase region since it requires mixing properties for regions ofarbitrary shape. An alternative approach, based on previous ideas of Oliveri, and Picco, is developed, which allows to establish results on rapid approach to equilibrium deeply inside the one phase region. In particular, in the ferromagnetic case, we considerably improve some previous results by Holley and Aizenman and Holley. Our results are optimal in the sene that, for example, they show for the first time fast convergence of the dynamicsfor any temperature above the critical one for thed-dimensional Ising model with or without an external field. In part II we extensively consider the general case (not necessarily attractive) and we develop a new method, based on renormalizations group ideas and on an assumption of strong mixing in a finite cube, to prove hypercontractivity of the Markov semigroup of the Glauber dynamics. We study discrete time Glauber dynamics for random configurations with local constraints (e.g. proper coloring, Ising and Potts models) on finite graphs with n vertices and of bounded degree. We show that the relaxation time (defined as the reciprocal of the spectral gap 1- spl lambda sub 2 ) for the dynamics on trees and on certain hyperbolic graphs, is polynomial in n. For these hyperbolic graphs, this yields a general polynomial sampling algorithm for random configurations. We then show that if the relaxation time spl tau sub 2 satisfies spl tau sub 2 =O(n), then the correlation coefficient, and the mutual information, between any local function (which depends only on the configuration in a fixed window) and the boundary conditions, decays exponentially in the distance between the window and the boundary. For the Ising model on a regular tree, this condition is sharp. The Ising model is widely regarded as the most studied model of spin-systems in statistical physics. The focus of this paper is its dynamic (stochastic) version, the Glauber dynamics, introduced in 1963 and by now the most popular means of sampling the Ising measure. Intensive study throughout the last three decades has yielded a rigorous understanding of the spectral-gap of the dynamics on ( Z ^2 ) everywhere except at criticality. While the critical behavior of the Ising model has long been the focus for physicists, mathematicians have only recently developed an understanding of its critical geometry with the advent of SLE, CLE and new tools to study conformally invariant systems.