A SYSTEMATIC SCAN FOR 7-COLOURINGS OF THE GRID
Markus Jalsenius, KASPER PEDERSEN · International Journal of Foundations of Computer Science · 2008
We study the mixing time of a systematic scan Markov chain for sampling from the uniform distribution on proper 7-colourings of a finite rectangular sub-grid of the infinite square lattice, the grid. A systematic scan Markov chain cycles through finite-size subsets of vertices in a deterministic order and updates the colours assigned to the vertices of each subset. The systematic scan Markov chain that we present cycles through subsets consisting of 2×2 sub-grids and updates the colours assigned to the vertices using a procedure known as heat-bath. We give a computer-assisted proof that this systematic scan Markov chain mixes in O( log n) scans, where n is the size of the rectangular sub-grid. We make use of a heuristic to compute required couplings of colourings of 2×2 sub-grids. This is the first time the mixing time of a systematic scan Markov chain on the grid has been shown to mix for less than 8 colours. We also give partial results that underline the challenges of proving rapid mixing of a systematic scan Markov chain for sampling 6-colourings of the grid by considering 2×3 and 3×3 sub-grids.