A Systematic Scan for 7-colourings of the Grid
| dc.creator | Jalsenius, Markus | |
| dc.creator | Pedersen, Kasper | |
| dc.date | 2007-04-12 | |
| dc.date | 2009-04-01 | |
| dc.date.accessioned | 2026-07-07T12:58:16Z | |
| dc.date.available | 2026-07-07T12:58:16Z | |
| dc.description | 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 2x2 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 2x2 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 2x3 and 3x3 sub-grids. | |
| dc.description | 16 pages, 4 figures, minor details changed (mostly typos) | |
| dc.identifier | https://arxiv.org/abs/0704.1625 | |
| dc.identifier | http://arxiv.org/abs/0704.1625 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/225187 | |
| dc.subject | Probability | |
| dc.subject | 60J10 | |
| dc.title | A Systematic Scan for 7-colourings of the Grid | |
| dc.type | text |