Local uniformity properties for glauber dynamics on graph colorings | Zendy

Hayes Thomas P. | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research