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

This is a preprint of an article published in the journal Random Structures & Algorithms, 18(2), 101-115. The journal is located at the following Wiley URL: http://www3.interscience.wiley.com/cgi-bin/jhome/38107We 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