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

摘要

We introduce a new technique for analyzing the mixing rate of Markov chains. We use it to prove that the Glauber dynamics on 2 Delta -colorings of a graph with maximum degree Delta 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. (C) 2001 John Wiley & Sons, Inc. [References: 14]