Local uniformity properties for glauber dynamics on graph colorings1. Issue 2 (27th June 2013)

• Record Type: Journal Article
• Authors: Hayes, Thomas P.
• Is Part Of: Random structures & algorithms. Volume 43:Issue 2(2013)
• Page Start: 139
• Page End: 180
• Publication Date: 2013-06-27
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20502
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>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. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 2013</p> </abstract>