Name
Abstract | ||
|---|---|---|
We study the mixing time of the Glauber dynamics for general spin systems on the regular tree, including the Ising model, the hard-core model (independent sets), and the antiferromagnetic Potts model at zero temperature (colorings). We generalize a framework, developed in our recent paper (Martinelli, Sinclair, and Weitz, Tech. Report UCB//CSD-03-1256, Dept. of EECS, UC Berkeley, July 2003) in the context of the Ising model, for establishing mixing time O(nlog n), which ties this property closely to phase transitions in the underlying model. We use this framework to obtain rapid mixing results for several models over a significantly wider range of parameter values than previously known, including situations in which the mixing time is strongly dependent on the boundary condition. We also discuss applications of our framework to reconstruction problems on trees. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007 A preliminary version of this paper appeared in Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms, January 2004. This work was done while the author was visiting the Departments of EECS and Statistics, University of California, Berkeley, supported in part by a Miller Visiting Professorship. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1002/rsa.v31:2 | Symposium on Discrete Algorithms |
Keywords | Field | DocType |
independent set,phase transitions,phase transition,ising model,mixing time,boundary condition | Glauber,Discrete mathematics,Boundary value problem,Spin-½,Combinatorics,Rapid mixing,Ising model,Mathematics,Potts model | Journal |
Volume | Issue | ISSN |
31 | 2 | 1042-9832 |
ISBN | Citations | PageRank |
0-89871-558-X | 36 | 3.07 |
References | Authors | |
13 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fabio Martinelli | 1 | 38 | 3.84 |
| Alistair Sinclair | 2 | 1506 | 308.40 |
| Dror Weitz | 3 | 258 | 19.56 |