Randomly colouring random graphs

<p>We consider the problem of generating a coloring of the random graph <em></em>_{<em>n</em>,<em>p</em>} uniformly at random using a natural Markov chain algorithm: the Glauber dynamics. We assume that there are <em>β</em><em>Δ</em> colors available, where <em>Δ</em> is the maximum degree of the graph, and we wish to determine the least <em>β</em> = <em>β</em>(<em>p</em>) such that the distribution is close to uniform in <em>O</em>(<em>n</em> log <em>n</em>) steps of the chain. This problem has been previously studied for <em></em>_{<em>n</em>,<em>p</em>} in cases where <em>n</em><em>p</em> is relatively small. Here we consider the “dense” cases, where <em>n</em><em>p</em> ε [<em>ω</em> ln <em>n</em>, <em>n</em>] and <em>ω</em> = <em>ω</em>(<em>n</em>) ∞. Our methods are closely tailored to the random graph setting, but we obtain considerably better bounds on <em>β</em>(<em>p</em>) than can be achieved using more general techniques.</p>