← All problems

Polynomial mixing conjecture for Glauber dynamics on graph colorings

For every finite graph G=(V,E)G=(V,E) with maximum degree Δ\Delta and every integer q≥Δ+2q\geq \Delta+2, the lazy Glauber dynamics on the set of proper qq-colorings of GG has mixing time bounded by a polynomial in ∣V∣|V|.

References

Progress summary

Refreshed
Open · progress reported

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 Δ\Delta with at least Δ+2\Delta+2 colors.

Known results

  • Jerrum, 1995: rapid mixing when q>2Δq>2\Delta.
  • Dyer, Goldberg, Greenhill, Jerrum, and Mitzenmacher, 2000: O(nlog⁡n)O(n\log n) mixing for triangle-free regular graphs when q≥(2−η)Δq\ge (2-\eta)\Delta.
  • Chen, Delcourt, Moitra, Perarnau, and Postle, 2019: general-graph mixing for q≥(11/6−ε0)Δq\ge (11/6-\varepsilon_0)\Delta.
  • Chen, Galanis, and Stefankovic, 2020: for triangle-free graphs, mixing when q≥αΔ+1q\ge \alpha\Delta+1 with α>α∗≈1.763\alpha>\alpha^*\approx1.763.

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 q≥1.7408Δq\ge1.7408\Delta. This improves the cited general coefficient but does not prove the Δ+2\Delta+2 conjecture, and the claim is unverified in the retrieved evidence.

Current status (as of October 2026): The general Δ+2\Delta+2 conjecture remains open; a preprint claims polynomial mixing for q≥1.7408Δq\ge1.7408\Delta, but that claim is unverified.

Sources

Solutions 0

No solutions have been posted yet.