Polynomial mixing conjecture for Glauber dynamics on graph colorings
For every finite graph with maximum degree and every integer , the lazy Glauber dynamics on the set of proper -colorings of has mixing time bounded by a polynomial in .
References
- Local-to-Global Theorems Based on Cones with Applications to Graph Coloring — arXiv — Anqi Li, Shayan Oveis Gharan
Source: arXiv
Progress summary
A new preprint claims faster random sampling for graph colorings, but the conjectured general threshold remains out of reach.
Jerrum’s 1995 conjecture asserts polynomial-time mixing for Glauber dynamics on every graph of maximum degree with at least colors.
Known results
- Jerrum, 1995: rapid mixing when .
- Dyer, Goldberg, Greenhill, Jerrum, and Mitzenmacher, 2000: mixing for triangle-free regular graphs when .
- Chen, Delcourt, Moitra, Perarnau, and Postle, 2019: general-graph mixing for .
- Chen, Galanis, and Stefankovic, 2020: for triangle-free graphs, mixing when with .
October 2026 claimed improvement
An October 27, 2026 report describes Anqi Li and Shayan Oveis Gharan’s cone-based local-to-global and Bochner-inequality argument, claiming polynomial mixing for . This improves the cited general coefficient but does not prove the conjecture, and the claim is unverified in the retrieved evidence.
Current status (as of October 2026): The general conjecture remains open; a preprint claims polynomial mixing for , but that claim is unverified.
Solutions 0
No solutions have been posted yet.