Very rapidly mixing Markov chains for 2Δ‐colorings and for independent sets in a graph with maximum degree 4 | Zendy

Molloy Michael | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

Very rapidly mixing Markov chains for 2Δ‐colorings and for independent sets in a graph with maximum degree 4

Author(s) -

Molloy Michael

Publication year - 2001

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/1098-2418(200103)18:2<101::aid-rsa1000>3.0.co;2-d

Subject(s) - glauber , markov chain , degree (music) , combinatorics , mixing (physics) , mathematics , markov chain mixing time , discrete mathematics , graph , markov model , variable order markov model , statistics , physics , quantum mechanics , acoustics , scattering , optics

We introduce a new technique for analyzing the mixing rate of Markov chains. We use it to prove that the Glauber dynamics on 2Δ‐colorings of a graph with maximum degree Δ mixes in O ( n log n ) time. We prove the same mixing rate for the Insert/Delete/Drag chain of Dyer and Greenhill ( Random Structures Algorithms 13 , 285–317 (1998)) on independent sets of graphs with maximum degree 4. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 101–115, 2001

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research