Premium
Local uniformity properties for glauber dynamics on graph colorings
Author(s) -
Hayes Thomas P.
Publication year - 2013
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20502
Subject(s) - glauber , markov chain , mathematics , random graph , graph , sampling (signal processing) , discrete mathematics , convergence (economics) , class (philosophy) , combinatorics , computer science , statistics , artificial intelligence , physics , filter (signal processing) , scattering , optics , economics , computer vision , economic growth
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