On forced periodicity of perfect colorings

DOI10.1007/S00224-023-10127-XzbMATH Open1526.37018arXiv2301.05232MaRDI QIDQ6174652FDOQ6174652

Jarkko Kari, Pyry Herva

Publication date: 17 August 2023

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

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.

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)

Cites Work

• Ideals, Varieties, and Algorithms
• Title not available (Why is that?)
• Theory of cellular automata: a survey
• Title not available (Why is that?)
• An Introduction to Symbolic Dynamics and Coding
• Title not available (Why is that?)
• Tiling the line with translates of one tile
• Title not available (Why is that?)
• Cellular Automata and Groups
• Title not available (Why is that?)
• Shorter Note: The Converse of Moore's Garden-of-Eden Theorem
• Title not available (Why is that?)
• Tesselation of integers
• On periodicity of generalized two-dimensional infinite words
• On multiple coverings of the infinite rectangular grid with balls of constant radius
• Perfect colorings of radius \(r>1\) of the infinite rectangular grid
• Title not available (Why is that?)
• An algebraic geometric approach to Nivat's conjecture
• The structure of translational tilings in $\mathbb{Z}^d$
• On perfect coverings of two-dimensional grids
• Low-complexity tilings of the plane
• Periodicity and decidability of tilings of ℤ2
• Nivat's conjecture and pattern complexity in algebraic subshifts
• Aperiodic two-dimensional words of small abelian complexity

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)