@inproceedings{057263d9f45d4113be2f480afd747c97,
title = "A non-Markovian coupling for randomly sampling colorings",
abstract = "We study a simple Markov chain, known as the Glauber dynamics, for randomly sampling (proper) k-colorings of an input graph G on n vertices with maximum degree Δ and girth g. We prove the Glauber dynamics is close to the uniform distribution after O(n log n) steps whenever k > (1 + ε)Δ, for all ε > 0, assuming g ≥ 9 and Δ = Ω(log n). The best previously known bounds were k > 11Δ/6 for general graphs, and k > 1.489Δ for graphs satisfying girth and maximum degree requirements. Our proof relies on the construction and analysis of a non-Markovian coupling. This appears to be the first application of a non-Markovian coupling to substantially improve upon known results.",
keywords = "Antiferromagnetic materials, Character generation, Chromium, Computational modeling, Computer science, Computer simulation, Mathematics, Physics, Polynomials, Sampling methods",
author = "Hayes, \{T. P.\} and E. Vigoda",
note = "Publisher Copyright: {\textcopyright} 2003 IEEE.; 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003 ; Conference date: 11-10-2003 Through 14-10-2003",
year = "2003",
doi = "10.1109/SFCS.2003.1238234",
language = "English",
series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",
publisher = "IEEE Computer Society",
pages = "618--627",
booktitle = "Proceedings - 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003",
address = "United States",
}