Polynomial mixing-time conjecture for Glauber dynamics on graph colourings

At least 5 years old · documented by

Let GG be a graph with maximum degree 4Δ44\Delta4, and let kk be an integer satisfying

k≥Δ+2.k \geq \Delta+2.

Consider the Glauber dynamics on the set of kk-colourings of GG, in which a uniformly random vertex is recoloured with a uniformly random available colour.

Polynomial mixing-time conjecture. For any graph GG, the Glauber dynamics on the kk-colourings of GG for k≥Δ+2k\geq\Delta+2 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

Never refreshed

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.