{
  "id": "0802.3487",
  "version": "v2",
  "published": "2008-02-24T03:59:15.000Z",
  "updated": "2008-05-23T21:52:36.000Z",
  "title": "Reconstruction of Random Colourings",
  "authors": [
    "Allan Sly"
  ],
  "comment": "Added references, updated notation",
  "doi": "10.1007/s00220-009-0783-7",
  "categories": [
    "math.PR"
  ],
  "abstract": "Reconstruction problems have been studied in a number of contexts including biology, information theory and and statistical physics. We consider the reconstruction problem for random $k$-colourings on the $\\Delta$-ary tree for large $k$. Bhatnagar et. al. showed non-reconstruction when $\\Delta \\leq \\frac12 k\\log k - o(k\\log k)$ and reconstruction when $\\Delta \\geq k\\log k + o(k\\log k)$. We tighten this result and show non-reconstruction when $\\Delta \\leq k[\\log k + \\log \\log k + 1 - \\ln 2 -o(1)]$ and reconstruction when $\\Delta \\geq k[\\log k + \\log \\log k + 1+o(1)]$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2008-05-23T21:52:36.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "82B26",
      "60K35"
    ],
    "keywords": [
      "random colourings",
      "reconstruction problem",
      "information theory",
      "ary tree",
      "statistical physics"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "publisher": "Springer",
      "journal": "Communications in Mathematical Physics",
      "year": 2009,
      "month": "Jun",
      "volume": 288,
      "number": 3,
      "pages": 943
    },
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009CMaPh.288..943S"
    }
  }
}