Recoloring infinite paths
Suppose you have a uniformly random 3-coloring of a doubly-infinite path graph. This can be generated by choosing any one vertex, choosing any one of the three colors for it, and then propagating the coloring outwards from it, choosing one of the two available colors for each successive vertex. It’s convenient to imagine the three colors as being represented by the three numbers 0, 1, and 2 mod 3. Now perform the following process, repeatedly: change the color of every cell whose two neighbors both have the color that is one plus its color (mod 3). In other words, the middle vertex of a triple of vertices that is colored 1–0–1 changes to color 2, the middle vertex of 2–1–2 changes to 0, and the middle vertex of 0–2–0 changes to 1. What does this do to the coloring?
You might think that it stays uniformly random, but it doesn’t. What happens is that you get increasingly large 2-colored regions, whose typical size is proportional to the square root of the number of recoloring steps, separated by triples of vertices that use all three colors. Within each 2-colored region, each recoloring step changes one of the two colors to the third color. The 3-colored triples form the boundaries between these regions and move leftwards or rightwards (depending on the ordering of their three colors). When two boundaries moving in opposite directions collide, they annihilate each other, leaving a larger 2-colored region.
I think the easiest way to see this is to use height functions for colorings. As described in my previous post, a height function is a mapping from the vertices to integers (the heights of the vertices), so that taking the height of each vertex mod 3 gives its color, and such that neighboring vertices have heights that differ by \(\pm 1\). It’s easy to construct these for colorings of the infinite path, again by starting from an arbitrary choice of height for a single arbitrarily-chosen vertex and propagating outwards. More strongly, for infinite bipartite graphs, the existence of height functions is equivalent to the non-existence of certain special graph homomorphisms to a six-cycle, as described for the finite case in my previous post. However in the infinite case the existence of height functions does not ensure the connectivity of the space of 3-colorings; for instance there is no way to change the infinite periodic 3-coloring …0–1–2–0–1–2… into anything else.
In terms of height functions, what’s happening in each recoloring step is that the height increases by two at each of its local minima. You can think of the height function as giving the height of a pile of particles over each vertex; then each recoloring step adds a particle wherever it can sit in place without rolling downhill.
The image above is one I drew several years ago for the Wikipedia article on cellular automaton rule 184. This cellular automaton has two states per cell (which we might as well think of as 1 and 0), and it acts by repeatedly swapping the states of pairs of consecutive cells containing the pattern 10. In the figure, the 1’s and 0’s translate to pieces of surface boundary that slope downwards or upwards (respectively), so a 10 pattern is a local minimum of the surface, and filling it in gives a 10 instead.
Rule 184 has an amazing variety of seemingly-unrelated interpretations; for instance, you can think of the cells of the automaton as a gridlocked highway, and the cells with 1’s in them as the cars of a traffic jam (perhaps stuck in traffic for their Thanksgiving Day travels). When a 1 has an open space ahead of it (a 0 cell) it moves forward, and otherwise it stays in place. This seemingly basic model displays a lot of the same features of real traffic such as freely flowing traffic when the total number of vehicles is small but waves of stop-and-go motion when the number of vehicles is high. It forms the basis for many more-sophisticated models of traffic flow.
But it is a different interpretation of Rule 184 that works best for understanding the question I started with, of what happens to a random coloring under recoloring operations. These operations are exactly what happens when you apply Rule 184 to the height function of a random coloring. But you can also view Rule 184 as describing a system of two kinds of particles, left-moving ones (11 patterns) and right-moving ones (00 patterns), separated by empty space (alternating 0’s and 1’s), that annihilate each other when they collide. In terms of the coloring, these particles are just the triples of vertices colored with three colors, and the parts of the cellular automaton with no particles are the 2-colored regions. The uniformly random coloring that we started with has the convenient property that particles of both types are equally likely. A right-moving particle will survive to step \(n\) if, in every prefix of the random sequence of particles to the right of it of length proportional to \(n\), there are more right-moving particles than left-moving particles. A standard calculation on random walks shows that this survival probability is \(\Theta(1/\sqrt{n})\), and this is also the density of remaining particles after \(n\) steps.