{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T15:33:09Z","timestamp":1759073589780},"reference-count":21,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2020,10,19]],"date-time":"2020-10-19T00:00:00Z","timestamp":1603065600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2021,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study and classify proper <jats:italic>q<\/jats:italic>-colourings of the \u2124<jats:italic><jats:sup>d<\/jats:sup><\/jats:italic> lattice, identifying three regimes where different combinatorial behaviour holds. (1) When <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000395_inline2.png\" \/><jats:tex-math>\n$q\\le d+1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, there exist frozen colourings, that is, proper <jats:italic>q<\/jats:italic>-colourings of \u2124<jats:italic><jats:sup>d<\/jats:sup><\/jats:italic> which cannot be modified on any finite subset. (2) We prove a strong list-colouring property which implies that, when <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000395_inline3.png\" \/><jats:tex-math>\n$q\\ge d+2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, any proper <jats:italic>q<\/jats:italic>-colouring of the boundary of a box of side length <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000395_inline4.png\" \/><jats:tex-math>\n$n \\ge d+2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> can be extended to a proper <jats:italic>q<\/jats:italic>-colouring of the entire box. (3) When <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000395_inline5.png\" \/><jats:tex-math>\n$q\\geq 2d+1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, the latter holds for any <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000395_inline6.png\" \/><jats:tex-math>\n$n \\ge 1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Consequently, we classify the space of proper <jats:italic>q<\/jats:italic>-colourings of the \u2124<jats:italic><jats:sup>d<\/jats:sup><\/jats:italic> lattice by their mixing properties.<\/jats:p>","DOI":"10.1017\/s0963548320000395","type":"journal-article","created":{"date-parts":[[2020,10,19]],"date-time":"2020-10-19T08:39:07Z","timestamp":1603096747000},"page":"360-373","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":4,"title":["Mixing properties of colourings of the \u2124<i><sup>d<\/sup><\/i> lattice"],"prefix":"10.1017","volume":"30","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[]},{"given":"Raimundo","family":"Brice\u00f1o","sequence":"additional","affiliation":[]},{"given":"Nishant","family":"Chandgotia","sequence":"additional","affiliation":[]},{"given":"Alexander","family":"Magazinov","sequence":"additional","affiliation":[]},{"given":"Yinon","family":"Spinka","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2020,10,19]]},"reference":[{"key":"S0963548320000395_ref1","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1006\/jctb.1999.1910","article-title":"Coloring graphs with sparse neighborhoods","volume":"77","author":"Alon","year":"1999","journal-title":"J. Combin. Theory Ser. B"},{"key":"S0963548320000395_ref3","doi-asserted-by":"crossref","first-page":"4617","DOI":"10.1090\/S0002-9947-10-05003-8","article-title":"Multidimensional sofic shifts without separation and their factors","volume":"362","author":"Boyle","year":"2010","journal-title":"Trans. Amer. Math. Soc."},{"key":"S0963548320000395_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-7152(02)00054-8"},{"key":"S0963548320000395_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-016-9807-1"},{"key":"S0963548320000395_ref4","doi-asserted-by":"crossref","first-page":"1658","DOI":"10.1017\/etds.2016.107","article-title":"The topological strong spatial mixing property and new conditions for pressure approximation","volume":"38","author":"Brice\u00f1o","year":"2018","journal-title":"Ergodic Theory Dynam. Systems"},{"key":"S0963548320000395_ref13","doi-asserted-by":"crossref","first-page":"909","DOI":"10.1007\/s11856-016-1398-2","article-title":"Markov random fields, Markov cocycles and the 3-colored chessboard","volume":"215","author":"Chandgotia","year":"2016","journal-title":"Israel J. Math."},{"key":"S0963548320000395_ref20","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1995.170.237"},{"key":"S0963548320000395_ref8","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1935"},{"key":"S0963548320000395_ref15","unstructured":"[15] Johansson, A. (1996) Asymptotic choice number for triangle free graphs. DIMACS technical report."},{"key":"S0963548320000395_ref2","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/BF01204715","article-title":"Colorings and orientations of graphs","volume":"12","author":"Alon","year":"1992","journal-title":"Combinatorica"},{"key":"S0963548320000395_ref5","first-page":"1868","article-title":"Dismantlability, Connectedness, and Mixing in Relational Structures, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)","volume":"132","author":"Brice\u00f1o","year":"2019","journal-title":"Leibniz International Proceedings in Informatics (LIPIcs)"},{"key":"S0963548320000395_ref9","first-page":"247","article-title":"Random colorings of a Cayley tree","volume":"10","author":"Brightwell","year":"2002","journal-title":"Contemporary Combinatorics"},{"key":"S0963548320000395_ref10","doi-asserted-by":"publisher","DOI":"10.1017\/S0143385700007859"},{"key":"S0963548320000395_ref19","unstructured":"[19] Peled, R. and Spinka, Y. (2018) Rigidity of proper colorings of \u2124 d . arXiv:1808.03597"},{"key":"S0963548320000395_ref21","unstructured":"[21] Sheffield, S. (2005) Random Surfaces (Ast\u00e9risque 304). Soci\u00e9t\u00e9 math\u00e9matique de France."},{"key":"S0963548320000395_ref7","doi-asserted-by":"publisher","DOI":"10.1137\/16M1066178"},{"key":"S0963548320000395_ref12","doi-asserted-by":"crossref","first-page":"41","DOI":"10.2140\/pjm.2018.294.41","article-title":"Mixing properties for hom-shifts and the distance between walks on associated graphs","volume":"294","author":"Chandgotia","year":"2018","journal-title":"Pacific J. Math."},{"key":"S0963548320000395_ref11","unstructured":"[11] Chandgotia, N. (2018) A short note on the pivot property. http:\/\/math.huji.ac.il\/~nishant\/Research_files\/Notes_files\/Pivot.pdf"},{"key":"S0963548320000395_ref6","doi-asserted-by":"crossref","first-page":"5129","DOI":"10.1090\/proc\/14267","article-title":"Factoring onto \u2124d subshifts with the finite extension property.","volume":"146","author":"Brice\u00f1o","year":"2018","journal-title":"Proc. Amer. Math. Soc."},{"key":"S0963548320000395_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-015-1178-4"},{"key":"S0963548320000395_ref14","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20518"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000395","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,13]],"date-time":"2021-04-13T11:58:45Z","timestamp":1618315125000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000395\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,19]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["S0963548320000395"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000395","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,10,19]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}