Polynomial mixing-time conjecture for Glauber dynamics on graph colourings
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Marc Heinrich, “Glauber dynamics for colourings of chordal graphs and graphs of bounded treewidth”, arXiv:2010.16158 (2020).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.