{
  "id": "1412.3156",
  "version": "v1",
  "published": "2014-12-09T23:23:49.000Z",
  "updated": "2014-12-09T23:23:49.000Z",
  "title": "Glauber Dynamics of colorings on trees",
  "authors": [
    "Allan Sly",
    "Yumeng Zhang"
  ],
  "comment": "25 pages",
  "categories": [
    "math.PR"
  ],
  "abstract": "The mixing time of the Glauber dynamics for spin systems on trees is closely related to reconstruction problem. Martinelli, Sinclair and Weitz established this correspondence for a class of spin systems with soft constraints bounding the log-Sobolev constant by a comparison with the block dynamics. However, when there are hard constraints, the block dynamics may be reducible. We introduce a variant of the block dynamics extending these results to a wide class of spin systems with hard constraints. This applies for essentially any spin system that has non-reconstruction provided that on average the root is not locally frozen in a large neighborhood. In particular we prove that the mixing time of the Glauber dynamics for colorings on the regular tree is $O(n\\log n)$ in the entire known non-reconstruction regime.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-12-09T23:23:49.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "glauber dynamics",
      "spin system",
      "block dynamics",
      "hard constraints",
      "mixing time"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 25,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1412.3156S"
    }
  }
}