Mixing properties of colourings of the Zd lattice

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

doi:10.1017/S0963548320000395

Mixing properties of colourings of the Z^d lattice

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

Mathematics

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

We study and classify proper q-colourings of the Z^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 Z^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 Z^d lattice by their mixing properties.

Original language	English (US)
Journal	Combinatorics Probability and Computing
DOIs	https://doi.org/10.1017/S0963548320000395
State	Accepted/In press - 2020

All Science Journal Classification (ASJC) codes

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

Access to Document

10.1017/S0963548320000395

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

@article{41cef6a4f87d40a984b23e1c7c1499f9,

title = "Mixing properties of colourings of the Zd lattice",

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.",

author = "Noga Alon and Raimundo Brice{\~n}o and Nishant Chandgotia and Alexander Magazinov and Yinon Spinka",

year = "2020",

doi = "10.1017/S0963548320000395",

language = "English (US)",

journal = "Combinatorics Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

}

TY - JOUR

T1 - Mixing properties of colourings of the Zd lattice

AU - Alon, Noga

AU - Briceño, Raimundo

AU - Chandgotia, Nishant

AU - Magazinov, Alexander

AU - Spinka, Yinon

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

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

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

SN - 0963-5483