Cereceda's conjecture

The fact that the Glauber dynamics converges to the uniform distribution on (d + 2)-colorings naturally raises the question of how quickly it converges. That is, what is the mixing time? A lower bound on the mixing time is the diameter of the space of colorings, the maximum (over pairs of colorings) of the number of steps needed to change one coloring of the pair into the other. If the diameter is exponentially large in the number n of vertices in the graph, then the Glauber dynamics on colorings is certainly not rapidly mixing. On the other hand, when the diameter is bounded by a polynomial function of n, this suggests that the mixing time might also be polynomial. In his 2007 doctoral dissertation, Cereceda investigated this problem, and found that (even for connected components of the space of colors) the diameter can be exponential for (d + 1)-colorings of d-degenerate graphs. On the other hand, he proved that the diameter of the color space is at most quadratic (or, in big O notation, O(n²)) for colorings that use at least 2d + 1 colors. He wrote that "it remains to determine" whether the diameter is polynomial for numbers of colors between these two extremes, or whether it is "perhaps even quadratic".^[5]

Although Cereceda asked this question for a range of colors and did not phrase it as a conjecture, by 2018 a form of this question became known as Cereceda's conjecture. This unproven hypothesis is the most optimistic possibility among the questions posed by Cereceda: that for graphs with degeneracy at most d, and for (d + 2)-colorings of these graphs, the diameter of the space of colorings is O(n²).^[6][7][8][9] If true, this would be best possible, as the space of 3-colorings of a path graph has quadratic diameter.^[10]

Although Cereceda's conjecture itself remains open even for degeneracy d = 2, it is known that for any fixed value of d the diameter of the space of (d + 2)-colorings is polynomial (with a different polynomial for different values of d). More precisely, the diameter is O(n^{d + 1}). When the number of colors is at least (3d + 3)/2, the diameter is quadratic.^[7]

A related question concerns the possibility that, for numbers of colors greater than d + 2, the diameter of the space of colorings might decrease from quadratic to linear.^[7] Bousquet & Bartier (2019) suggest that this might be true whenever the number of colors is at least d + 3.^[9]

The Glauber dynamics is not the only way to change colorings of graphs into each other. Alternatives include the Kempe dynamics in which one repeatedly finds and swaps the colors of Kempe chains,^[8] and the "heat bath" dynamics in which one chooses pairs of adjacent vertices and a valid recoloring of that pair. Both of these kinds of moves include the Glauber one-vertex moves as a special case, as changing the color of one vertex is the same as swapping the colors on a Kempe chain that only includes that one vertex. These moves may have stronger mixing properties and lower diameter of the space of colorings. For instance, both the Kempe dynamics and the heat bath dynamics mix rapidly on 3-colorings of cycle graphs, whereas the Glauber dynamics is not even connected when the length of the cycle is not four.