{
  "id": "1206.3193",
  "version": "v1",
  "published": "2012-06-14T17:42:50.000Z",
  "updated": "2012-06-14T17:42:50.000Z",
  "title": "Torpid Mixing of Local Markov Chains on 3-Colorings of the Discrete Torus",
  "authors": [
    "David Galvin",
    "Dana Randall"
  ],
  "comment": "9 pages. Originally appeared in the proceedings of SODA 2007",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "We study local Markov chains for sampling 3-colorings of the discrete torus $T_{L,d}={0,..., L-1}^d$. We show that there is a constant $\\rho \\approx .22$ such that for all even $L \\geq 4$ and $d$ sufficiently large, certain local Markov chains require exponential time to converge to equilibrium. More precisely, if $\\cM$ is a Markov chain on the set of proper 3-colorings of $T_{L,d}$ that updates the color of at most $\\rho L^d$ vertices at each step and whose stationary distribution is uniform, then the convergence to stationarity of $\\cM$ is exponential in $L^{d-1}$. Our proof is based on a conductance argument that builds on sensitive new combinatorial enumeration techniques.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-06-14T17:42:50.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68R10",
      "68W25",
      "05C15"
    ],
    "keywords": [
      "discrete torus",
      "torpid mixing",
      "study local markov chains",
      "combinatorial enumeration techniques",
      "exponential time"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 9,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1206.3193G"
    }
  }
}