3-colorings of graphs are inherently a ternary thing, right? There are three choices for the color of each vertex. But, for 3-colorings of cycles, there's a way of looking at them in binary (as strings of bits) that may, I think, help simplify my still-unresolved TCSexchange question on random walks in the space of 3-colorings.

Fix a starting vertex of the cycle, and an orientation of the cycle. We'll assume that the three colors in a coloring are represented by the three numbers \( 0 \), \( 1 \), and \( 2 \) (mod \( 3 \)). From any proper coloring of an \( n \)-cycle, generate a sequence of \( n \) bits by walking around the cycle clockwise from the starting vertex and writing down a \( 1 \) bit whenever the color at a vertex differs from the color at the previous vertex by \( +1 \) (mod \( 3 \)), and writing down a \( 0 \) bit whenever the color at a vertex differs from the color at the previous vertex by \( -1 \) (mod \( 3 \)). If a sequence of bits can be generated from a coloring in this way, let's call it a "colorful sequence".

It's not hard to see that a bit sequence is colorful if and only if the number of 1 bits and the number of \( 0 \) bits are equal to each other mod \( 3 \), because then the total difference as one goes around the cycle from the starting vertex back to itself is \( 0 \) mod \( 3 \). For instance, for \( n = 5 \), there are ten colorful sequences: \( 10000 \), \(01000 \), \(00100 \), \(00010 \), \(00001 \), \(01111 \), \(10111 \), \(11011 \), \(11101 \), and \( 11110 \). For large \( n \) very close to \( 1/3 \) of the possible bit sequences are colorful: the number of \( 1 \)-bits is nearly equally likely to be any of the three values mod \( 3 \), but only one of these three values leads to colorful sequences. On the other hand, each colorful sequence encodes exactly three different colorings, because adding the same number (mod \( 3 \)) to the colors of all the vertices produces another valid coloring with the same bit sequence. These two factors of \( 1/3 \) and \( 3 \) cancel, explaining the fact that the number of \( 3 \)-colorings of an \( n \)-cycle is very close to \( 2^n \).

A colorful sequence of length \( n \) can be formed from a colorful sequence of length \( n-2 \) by adding \( 01 \) or \( 10 \) to the end, or it can be formed from a colorful sequence of length \( n-1 \) by flipping and repeating the final bit. Therefore, the number of colorful sequences of length \( n \) obey the same recurrence relation \( J_n = J_{n-1} + 2J_{n-2} \) that defines the Jacobsthal numbers, but with different initial conditions causing these numbers to be two times the Jacobsthal numbers, shifted over by one position.

A step in the Glauber dynamics (recoloring a single vertex of the cycle) looks, in this more abstract model of colorings, exactly like an operation that swaps the values of two cyclically adjacent bits. In my TCSexchange question, I originally wrote that Glauber steps don't work for \( n=5 \) (based on the picture of the space of colorings of the 5-cycle that I included in my previous post, which shows it breaking down into two \( 15 \)-cycles if you remove the non-Glauber moves), and I quickly amended that to add that it also doesn't work for cycle lengths that are a multiple of three (based on the coloring that repeats the same three colors around the cycle, from which no moves are possible). But in fact this analysis shows that Glauber moves are almost never enough, because they always preserve the number of \( 0 \)- and \( 1 \)-bits in the bitstring representing the coloring but there exist different colorings with different numbers of \( 0 \)- and \( 1 \)-bits. The only exception is the \( 4 \)-cycle, for which Glauber dynamics does work and for which all colorings use two \( 0 \)-bits and two \( 1 \)-bits.

If we take one step up from the Glauber moves, and look at the moves that change the colors of two adjacent vertices in the graph, then in the bitstring view of the world these moves take three cyclically adjacent bits with the same value and flip them: \( 000 \leftrightarrow 111 \). It seems obvious to me (though I know so little about techniques for proving rapid mixing that I don't know how to prove it) that these two kinds of moves, swapping two adjacent symbols and flipping three, are sufficient for rapid mixing on the set of colorful sequences, and it actually is obvious that they are sufficient to get from any colorful sequence to any other colorful sequence. For instance, on the five- and six-cycles, the state spaces they generate are shown below.

State space of 3-colorings on a 5-cycle

State space of 3-colorings on a 6-cycle

Proving rapid mixing on the set of colorful sequences isn't quite enough to prove rapid mixing on the set of 3-colorings: it's conceivable (though it seems unlikely to me) that there's a subset \( S \) of \( 1/3 \) of the colorings with the property that the colorful sequences map 1-1 to \( S \) and that it's very difficult to get from \( S \) to its complement. But it could be useful as a toy problem to test out ideas that will eventually solve the real one as well.