{
  "id": "1210.4232",
  "version": "v1",
  "published": "2012-10-16T02:32:12.000Z",
  "updated": "2012-10-16T02:32:12.000Z",
  "title": "Phase coexistence and torpid mixing in the 3-coloring model on Z^d",
  "authors": [
    "David Galvin",
    "Jeff Kahn",
    "Dana Randall",
    "Gregory Sorkin"
  ],
  "comment": "26 pages. arXiv admin note: substantial text overlap with arXiv:1206.3193",
  "categories": [
    "math.CO",
    "math-ph",
    "math.MP"
  ],
  "abstract": "We show that for all sufficiently large d, the uniform proper 3-coloring model (in physics called the 3-state antiferromagnetic Potts model at zero temperature) on Z^d admits multiple maximal-entropy Gibbs measures. This is a consequence of the following combinatorial result: if a proper 3-coloring is chosen uniformly from a box in Z^d, conditioned on color 0 being given to all the vertices on the boundary of the box which are at an odd distance from a fixed vertex v in the box, then the probability that v gets color 0 is exponentially small in d. The proof proceeds through an analysis of a certain type of cutset separating v from the boundary of the box, and builds on techniques developed by Galvin and Kahn in their proof of phase transition in the hard-core model on Z^d. Building further on these techniques, we study local Markov chains for sampling proper 3-colorings of the discrete torus Z^d_n. We show that there is a constant \\rho \\approx 0.22 such that for all even n \\geq 4 and d sufficiently large, if M is a Markov chain on the set of proper 3-colorings of Z^d_n that updates the color of at most \\rho n^d vertices at each step and whose stationary distribution is uniform, then the mixing time of M (the time taken for M to reach a distribution that is close to uniform, starting from an arbitrary coloring) is essentially exponential in n^{d-1}.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-10-16T02:32:12.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "82B20"
    ],
    "keywords": [
      "phase coexistence",
      "torpid mixing",
      "admits multiple maximal-entropy gibbs measures",
      "study local markov chains",
      "antiferromagnetic potts model"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 26,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1210.4232G"
    }
  }
}