On forced periodicity of perfect colorings

DOI10.1007/S00224-023-10127-XMaRDI QIDQ6174652zbMATH OpenFDO

Authors Pyry Herva, Jarkko Kari

Publication date 17 August 2023

Published in Theory of Computing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2301.05232

zbMATH Keywords

perfect coloringsforced periodicityinfinite grid graphsmulti-dimensional symbolic dynamics

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Symbolic dynamics (37B10)

Abstract: We study forced periodicity of two-dimensional configurations under certain constraints and use an algebraic approach to multidimensional symbolic dynamics in which $d$-dimensional configurations and finite patterns are presented as formal power series and Laurent polynomials, respectively, in $d$ variables. We consider perfect colorings that are configurations such that the number of points of a given color in the neighborhood of any point depends only on the color of the point for some fixed relative neighborhood, and we show that by choosing the alphabet suitably any perfect coloring has a non-trivial annihilator, that is, there exists a Laurent polynomial whose formal product with the power series presenting the perfect coloring is zero. Using known results we obtain a sufficient condition for forced periodicity of two-dimensional perfect colorings. As corollaries of this result we get simple new proofs for known results of forced periodicity on the square and the triangular grids. Moreover, we obtain a new result concerning forced periodicity of perfect colorings in the king grid. We also consider perfect colorings of a particularly simple type: configurations that have low abelian complexity with respect to some shape, and we generalize a result that gives a sufficient condition for such configurations to be necessarily periodic. Also, some algorithmic aspects are considered.

Recommendations

• On periodicity of perfect colorings of the infinite hexagonal and triangular grids
• Perfect colorings of radius \(r>1\) of the infinite rectangular grid
• scientific article; zbMATH DE number 2097450
• On circular perfect two-color colorings
• Low-complexity tilings of the plane

Cites work

• scientific article; zbMATH DE number 524126 (Why is no real title available?)
• scientific article; zbMATH DE number 1024080 (Why is no real title available?)
• scientific article; zbMATH DE number 1024657 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 2042127 (Why is no real title available?)
• scientific article; zbMATH DE number 3205673 (Why is no real title available?)
• An Introduction to Symbolic Dynamics and Coding
• Aperiodic two-dimensional words of small abelian complexity
• Cellular automata and groups
• Ideals, Varieties, and Algorithms
• Low-complexity tilings of the plane
• Nivat's conjecture and pattern complexity in algebraic subshifts
• On multiple coverings of the infinite rectangular grid with balls of constant radius
• On perfect coverings of two-dimensional grids
• On periodicity of generalized two-dimensional infinite words
• Perfect colorings of radius \(r>1\) of the infinite rectangular grid
• Periodicity and decidability of tilings of \(\mathbb{Z}^2\)
• Shorter Note: The Converse of Moore's Garden-of-Eden Theorem
• Structural aspects of tilings
• Tesselation of integers
• The structure of translational tilings in \(\mathbb{Z}^d\)
• Theory of cellular automata: a survey
• Tiling the line with translates of one tile

Cited in

(1)

• On periodicity of perfect colorings of the infinite hexagonal and triangular grids

This page was built for publication: On forced periodicity of perfect colorings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6174652)