OP-00415 Open

Rapid sampling of proper colorings at the ergodicity threshold

Let $\Delta \ge 2$ and $q \ge \Delta + 2$ be integers, and let $G$ be a finite simple graph with $n$ vertices and maximum degree at most $\Delta$. The Glauber dynamics for proper $q$-colorings of $G$ chooses a uniform vertex and recolors it with a uniform color among those not used by its neighbours. Since $q \ge \Delta + 2$, it is irreducible on the proper $q$-colorings of $G$, and its stationary distribution is uniform on them. Jerrum proved that its mixing time to error $\varepsilon$ is at most $\bigl\lceil \frac{q - \Delta}{q - 2\Delta}\, n (\log n + \log(1/\varepsilon)) \bigr\rceil$ when $q > 2\Delta$, and Vigoda that it is $O(n^2 \log n)$ when $q > 11\Delta/6$. Chen and Liu (2026) proved rapid mixing when $q \ge (1 + \delta)\Delta$, for graphs of girth at least five whose maximum degree is large enough depending on $\delta > 0$.

Problem. For each such $\Delta$ and $q$, do there exist constants $C_{\Delta,q}, a_{\Delta,q} < \infty$ such that, for every such $G$ and every $0 < \varepsilon < 1/2$, the total-variation mixing time of this chain to error $\varepsilon$, from the worst starting proper coloring, is at most $C_{\Delta,q}\, n^{a_{\Delta,q}} \log(1/\varepsilon)$?

Source: Folklore, as the conjecture of O(n log n) mixing for q ≥ Δ + 2: Hayes at the ARCC workshop Sharp Thresholds for Mixing Times (2004), Open Question 30, and Frieze and Vigoda (2007); Levin and Peres (2017), Notes to Chapter 14, ask whether q > Δ + C gives polynomial mixing. Stated by AIM — Open Applied Problems in the polynomial form for q ≥ Δ + 2.

Imported from github.com/MColbrook/AIM.

Classification

Primary: PR — Probability
Secondary: CO
Keywords: AIM Open Applied Problems, Glauber dynamics, mixing times, proper colorings

References

@incollection{frieze2007,
  author    = {Frieze, Alan and Vigoda, Eric},
  title     = {A survey on the use of {M}arkov chains to randomly sample colourings},
  booktitle = {Combinatorics, Complexity, and Chance},
  editor    = {Grimmett, Geoffrey and McDiarmid, Colin},
  series    = {Oxford Lecture Ser. Math. Appl.},
  volume    = {34},
  publisher = {Oxford University Press},
  address   = {Oxford},
  year      = {2007},
  pages     = {53--71},
  doi       = {10.1093/acprof:oso/9780198571278.003.0004},
}
@misc{goel2004,
  author       = {Goel, Sharad and Nachmias, Asaf and Ralph, Peter and Shah, Devavrat},
  title        = {{ARCC} workshop: sharp thresholds for mixing times},
  howpublished = {Open problems from the workshop, American Institute of Mathematics, Palo Alto, December 20--23, 2004},
  year         = {2004},
  url          = {https://www.aimath.org/WWN/mixingtimes/mixingtimes.pdf},
  note         = {Scribed notes; Open Question 30, from the talk of Tom Hayes},
}
@book{levin2017,
  author    = {Levin, David A. and Peres, Yuval},
  title     = {Markov Chains and Mixing Times},
  edition   = {Second},
  note      = {With contributions by Elizabeth L. Wilmer},
  publisher = {American Mathematical Society},
  address   = {Providence, RI},
  year      = {2017},
  doi       = {10.1090/mbk/107},
}
@article{jerrum1995,
  author  = {Jerrum, Mark},
  title   = {A very simple algorithm for estimating the number of $k$-colorings of a low-degree graph},
  journal = {Random Structures Algorithms},
  volume  = {7},
  number  = {2},
  year    = {1995},
  pages   = {157--165},
  doi     = {10.1002/rsa.3240070205},
}
@article{vigoda2000,
  author  = {Vigoda, Eric},
  title   = {Improved bounds for sampling colorings},
  journal = {J. Math. Phys.},
  volume  = {41},
  number  = {3},
  year    = {2000},
  pages   = {1555--1569},
  doi     = {10.1063/1.533196},
}
@misc{chen2026,
  author        = {Chen, Xiaoyu and Liu, Kuikui},
  title         = {A spectral local-to-global principle for spin systems on graphs with girth at least five},
  year          = {2026},
  eprint        = {2608.25491},
  archivePrefix = {arXiv},
}
@misc{aim-coloring-glauber-threshold,
  author       = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
  title        = {{Rapid sampling of proper colorings at the ergodicity threshold}},
  howpublished = {AIM --- Open Applied Problems, GitHub repository},
  year         = {2026},
  url          = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/269-coloring-glauber-threshold.md},
  note         = {Entry 269 at commit a153f46, 2026-10-13},
}

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00415, "Rapid sampling of proper colorings at the ergodicity threshold", clopen.solutions.