Mixing properties of colourings of the Zd lattice

Noga Alon, Raimundo Briceño, Nishant Chandgotia, Alexander Magazinov, Yinon Spinka

Research output: Contribution to journalArticlepeer-review

Abstract

We study and classify proper q-colourings of the Zd lattice, identifying three regimes where different combinatorial behaviour holds. (1) When q ≦ d + 1, there exist frozen colourings, that is, proper q-colourings of Zd 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 Zd lattice by their mixing properties.

Original languageEnglish (US)
JournalCombinatorics Probability and Computing
DOIs
StateAccepted/In press - 2020

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Mixing properties of colourings of the Z<sup>d</sup> lattice'. Together they form a unique fingerprint.

Cite this