Paper Info
Title
Local uniformity properties for glauber dynamics on graph colorings.
Abstract
We investigate some local properties which hold with high probability for randomly selected colorings of a fixed graph with no short cycles. In a number of related works, establishing these particular properties has been a crucial step towards proving rapid convergence for the single-site Glauber dynamics, a Markov chain for sampling colorings uniformly at random. For a large class of graphs, this approach yields the most efficient known algorithms for sampling random colorings. (c) 2013 Wiley Periodicals, Inc.
Year
DOI
Venue
2013
10.1002/rsa.20502
RANDOM STRUCTURES & ALGORITHMS
Keywords
Field
DocType
Markov chains,mixing times,graph coloring
Glauber,Discrete mathematics,Random regular graph,Markov chain mixing time,Combinatorics,Random graph,Markov chain,Sampling (statistics),Greedy coloring,Mathematics,Graph coloring
Journal
Volume
Issue
ISSN
43.0
2.0
1042-9832
Citations 
PageRank 
References 
1
0.35
6
Authors
1
Name
Order
Citations
PageRank
Thomas P. Hayes165954.21