{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,30]],"date-time":"2023-10-30T08:25:16Z","timestamp":1698654316456},"reference-count":9,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2008,12]]},"abstract":"<jats:p> 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\u00d72 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\u00d72 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\u00d73 and 3\u00d73 sub-grids. <\/jats:p>","DOI":"10.1142\/s012905410800639x","type":"journal-article","created":{"date-parts":[[2009,1,5]],"date-time":"2009-01-05T09:36:29Z","timestamp":1231148189000},"page":"1461-1477","source":"Crossref","is-referenced-by-count":1,"title":["A SYSTEMATIC SCAN FOR 7-COLOURINGS OF THE GRID"],"prefix":"10.1142","volume":"19","author":[{"given":"MARKUS","family":"JALSENIUS","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Liverpool, Ashton Street, Liverpool, L69 3BX, United Kingdom"}]},{"given":"KASPER","family":"PEDERSEN","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Liverpool, Ashton Street, Liverpool, L69 3BX, United Kingdom"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1007\/11830924_31"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1214\/105051605000000683"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1112\/S1461157000001169"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20002"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704445470"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799360355"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74456-6_25"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1007\/BF02199113"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20073"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905410800639X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:32:56Z","timestamp":1565137976000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S012905410800639X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,12]]},"references-count":9,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2008,12]]}},"alternative-id":["10.1142\/S012905410800639X"],"URL":"https:\/\/doi.org\/10.1142\/s012905410800639x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,12]]}}}