✦ LIBER ✦

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

✍ Scribed by Michael Molloy

Publisher: John Wiley and Sons
Year: 2001
Tongue: English
Weight: 140 KB
Volume: 18
Category: Article
ISSN: 1042-9832
DOI: 10.1002/1098-2418(200103)18:2<101::aid-rsa1000>3.0.co;2-d

No coin nor oath required. For personal study only.

✦ Synopsis

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.