# Random 3-coloring of the square and cubic lattice

Joint work with Cris Moore.

A 3-coloring is a way of assigning one of the three colors 0, 1 and 2 to all vertices in a graph so that no vertex has the same color as any of its closest neighbors. The graph that is colored here is a square or cubic lattice with fixed boundary conditions. A 3-coloring is also equivalent to an antiferromagnetic 3 state Potts model at zero temperature. Sometimes models of this type have a height function, that can be very useful when the model is analysed. The height function of a 3-coloring is defined as follows: Assign an integer height value to one vertex and propagate the height out from that vertex to the rest of the lattice. When you move from one vertex to one of its neighbors and the color changes as if you added 1 modulo 3 the height increases by one and if the color changes as if you subtracted 1 modulo 3 the height decreases by 1.

0 -> 1, 1 -> 2, 2 -> 0 : Delta_h = +1

1 -> 0, 2 -> 1, 0 -> 2 : Delta_h = -1

It is easy to see that it is possible to reconstruct the 3-coloring from the height function as the color of a vertex is simply its height value modulo 3.

#### Examples of 3-colorings

Click on the thumbnails to see larger versions of the images.