Jerrum's Glauber-dynamics conjecture for graph colorings
Let be a graph of maximum degree , and consider the Glauber dynamics for sampling proper -colorings of . Jerrum's conjecture. The Glauber dynamics for sampling -colorings from mixes in polynomial time whenever . Efficient Glauber-dynamics sampling at this threshold would substantially improve the best general bounds for approximate sampling of proper colorings; the paper reports that the conjecture remains open, with known results requiring more colors.
References
- Zongchen Chen, Kuikui Liu, Nitya Mani and Ankur Moitra, “Strong spatial mixing for colorings on trees and its algorithmic applications”, arXiv:2304.01954 (2024).
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.