Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-16T19:48:07.248Z Has data issue: false hasContentIssue false

Mixing properties of colourings of the ℤd lattice

Published online by Cambridge University Press:  19 October 2020

Noga Alon
Affiliation:
Department of Mathematics, Princeton University, Princeton, NJ 08544, USA, and Schools of Mathematics and Computer Science, Tel Aviv University, Tel Aviv 6997801, Israel
Raimundo Briceño
Affiliation:
Pontificia Universidad Católica de Chile, Santiago, Chile
Nishant Chandgotia*
Affiliation:
School of Mathematical Sciences, Hebrew University of Jerusalem, Israel
Alexander Magazinov
Affiliation:
Higher School of Economics, National Research University, 6 Usacheva Street, Moscow 119048, Russia
Yinon Spinka
Affiliation:
University of British Columbia, Department of Mathematics, Vancouver, BC V6T 1Z2, Canada
*
*Corresponding author. Email: nishant.chandgotia@gmail.com
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We study and classify proper q-colourings of the ℤd lattice, identifying three regimes where different combinatorial behaviour holds. (1) When $q\le 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\ge d+2$, any proper q-colouring of the boundary of a box of side length $n \ge d+2$ can be extended to a proper q-colouring of the entire box. (3) When $q\geq 2d+1$, the latter holds for any $n \ge 1$. Consequently, we classify the space of proper q-colourings of the ℤd lattice by their mixing properties.

Information

Type
Paper
Copyright
© The Author(s), 2020. Published by Cambridge University Press