Rapidly mixing Markov chains on 3-colorings of a cycle

Question

The Glauber dynamics is a Markov chain on the colorings of a graph in which at each step one attempts to recolor a randomly chosen vertex with a random color. It does not mix for the 3-colorings of a 5-cycle: there are 30 3-colorings, but only 15 of them can be reached by single-vertex recoloring steps. More generally, it can be shown not to mix for 3-colorings of an n-cycle unless n=4.

The Kempe chain or Wang-Swendsen-Kotecký dynamics is only a little more complicated: at each step one chooses a random vertex v and a random color c, but then one finds the subgraph induced by two of the colors (c and the color of v) and swaps these colors within the component containing v. It is not hard to see that, unlike the Glauber dynamics, all 3-colorings of a cycle can be reached.

Is the Wang-Swendsen-Kotecký dynamics rapidly mixing on 3-colorings of an n-vertex cycle graph?

I know of the results e.g. by Molloy (STOC 2002) that Glauber is rapidly mixing when the number of colors is at least 1.489 times the degree (true here) and the graph to be colored has high girth (also true), but they also require that the degree be at least logarithmic in the size of the graph (not true for cycle graphs), so they don't seem to apply.

Answer 1

I got the following solution by email from Dana Randall, so any credit for the solution should go to her (which I guess means: don't upvote this answer) and any bugs were likely introduced by me.

The short version of Dana's solution is: instead of using the Markov chain I described, in which potentially-large two-colored regions are recolored, use a "heat bath" in which we repeatedly remove the colors of two vertices and then choose a valid coloring for them at random. It's not hard to show that, if this chain mixes, then the other one does as well. But a standard path coupling argument turns out to work to show that the heat bath does indeed mix.

The long version is too long to include here, so I put it in a blog post instead.