Abstract

Many Markov chain algorithms for generating random configurations in a graph (e.g. a random vertex-colouring or independent set) proceed by randomly modifying the label of a randomly selected vertex. It has long been regarded as "obvious" that such processes must always take $\Omega(n \log n)$ time to "get close" to the stationary distribution in an $n$-vertex graph. We will show how this intuition can be justified, and indicate why it is rather more difficult to prove than might first be supposed.

(Joint work with Leslie Goldberg and Eric Vigoda)