  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}.
