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 g raph 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 wi th maximum degree 4. (C) 2001 John Wiley & Sons, Inc.