ALCOMFT-TR-03-47

L. A. Goldberg, R. Martin and M. Paterson
Random sampling of 3-colourings in Z²
Warwick. Work package 4. September 2003.

Abstract: \usepackageamsfonts \def\zset\ensuremath\mathbbZ We consider the problem of uniformly sampling proper 3-colourings of an mx n rectangular region of \zset². We show that the single-site ``Glauber-dynamics'' Markov chain is rapidly mixing. Our result complements an earlier result of Luby, Randall and Sinclair, which demonstrates rapid mixing when there is a fixed boundary (whose colour cannot be changed).

Postscript file: ALCOMFT-TR-03-47.ps.gz (230 kb).