{
  "id": "math/0308284",
  "version": "v3",
  "published": "2003-08-28T20:13:52.000Z",
  "updated": "2004-03-26T04:40:33.000Z",
  "title": "Glauber Dynamics on Trees and Hyperbolic Graphs",
  "authors": [
    "Noam Berger",
    "Claire Kenyon",
    "Elchanan Mossel",
    "Yuval Peres"
  ],
  "comment": "To appear in Probability Theory and Related Fields",
  "categories": [
    "math.PR"
  ],
  "abstract": "We study continuous 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 $|\\lambda_1-\\lambda_2|$) for the dynamics on trees and on planar 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 $\\tau_2$ satisfies $\\tau_2=O(1)$, 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.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2004-03-26T04:40:33.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "relaxation time",
      "random configurations",
      "study continuous time glauber dynamics",
      "planar hyperbolic graphs",
      "general polynomial sampling algorithm"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2003math......8284B"
    }
  }
}