Paper Info
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 \Delta and girth g. We prove the Glauber dynamics is close to the uniform distribution after 0(n log n) steps whenever k (1 + \varepsilon)\Delta for all \varepsilon 0, assuming g 驴 9 and \Delta= \Omega (\log n). The best previously known bounds were k 11\Delta/6 for general graphs, and k 1.489\Delta 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.
Year
DOI
Venue
2003
10.1109/SFCS.2003.1238234
FOCS
Keywords
Field
DocType
general graph,maximum degree requirement,maximum degree,n vertex,randomly sampling colorings,known result,glauber dynamic,n log n,girth g,non-markovian coupling,log n,satisfiability,markov chain,computational complexity,markov processes,uniform distribution,sampling methods
Glauber,Binary logarithm,Discrete mathematics,Combinatorics,Vertex (geometry),Markov chain,Uniform distribution (continuous),Omega,Degree (graph theory),Time complexity,Mathematics
Conference
ISSN
ISBN
Citations 
0272-5428
0-7695-2040-5
25
PageRank 
References 
Authors
1.59
11
2
Name
Order
Citations
PageRank
Thomas P. Hayes165954.21
Eric Vigoda274776.55