TY - JOUR

T1 - Mixing properties of colourings of the ℤdlattice

AU - Alon, Noga

AU - Briceño, Raimundo

AU - Chandgotia, Nishant

AU - Magazinov, Alexander

AU - Spinka, Yinon

N1 - Funding Information:
The first author was supported by NSF grant DMS-1855464, ISF grant 281/17, BSF grant 2018267 and the Simons Foundation. The second author was supported by CONICYT/FONDECYT Postdoctorado 3190191 and European Research Council Starting Grants 678520 and 676970. The third author was funded by European Research Council Starting Grant 678520 (LocalOrder) and ISF grants 1289/17, 1702/17 and 1570/17. The fourth author was funded by European Research Council Starting Grant 678520 (LocalOrder).
Publisher Copyright:
© 2020 The Author(s). Published by Cambridge University Press.

PY - 2021/5/19

Y1 - 2021/5/19

N2 - We study and classify proper q-colourings of the ℤd lattice, identifying three regimes where different combinatorial behaviour holds. (1) When q ≤ d + 1, there exist frozen colourings, that is, proper q-colourings of ℤd which cannot be modified on any finite subset. (2) We prove a strong list-colouring property which implies that, when q ≥ d+2, any proper q-colouring of the boundary of a box of side length n ≥ d + 2 can be extended to a proper q-colouring of the entire box. (3) When q ≥ 2d+1, the latter holds for any n ≥ 1. Consequently, we classify the space of proper q-colourings of the ℤd lattice by their mixing properties.

AB - We study and classify proper q-colourings of the ℤd lattice, identifying three regimes where different combinatorial behaviour holds. (1) When q ≤ d + 1, there exist frozen colourings, that is, proper q-colourings of ℤd which cannot be modified on any finite subset. (2) We prove a strong list-colouring property which implies that, when q ≥ d+2, any proper q-colouring of the boundary of a box of side length n ≥ d + 2 can be extended to a proper q-colouring of the entire box. (3) When q ≥ 2d+1, the latter holds for any n ≥ 1. Consequently, we classify the space of proper q-colourings of the ℤd lattice by their mixing properties.

UR - http://www.scopus.com/inward/record.url?scp=85093690508&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85093690508&partnerID=8YFLogxK

U2 - 10.1017/S0963548320000395

DO - 10.1017/S0963548320000395

M3 - Article

AN - SCOPUS:85093690508

SN - 0963-5483

VL - 30

SP - 360

EP - 373

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

IS - 3

ER -