Polynomial mixing-time conjecture for Glauber dynamics on graph colourings
Let be a graph with maximum degree , and let be an integer satisfying
Consider the Glauber dynamics on the set of -colourings of , in which a uniformly random vertex is recoloured with a uniformly random available colour.
Polynomial mixing-time conjecture. For any graph , the Glauber dynamics on the -colourings of for has polynomial mixing time.
This conjecture asserts rapid mixing at the standard threshold of two more colours than the maximum degree. Polynomial mixing is important because it would make Glauber dynamics an efficient sampler for uniformly random proper colourings; the source presents this as a well-known conjecture and does not state a resolution.
References
Primary source
Marc Heinrich, “Glauber dynamics for colourings of chordal graphs and graphs of bounded treewidth”, arXiv:2010.16158 (2020).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.