17 November – Jarkko Kari: Low complexity colorings of the two-dimensional grid
A two-dimensional configuration is a coloring of the infinite grid ℤ² using a finite number of colors. For a finite subset D of ℤ², the D-patterns of a configuration are the patterns of shape D that appear in the configuration. We say the configuration is admitted by these patterns. The number of distinct D-patterns of a configuration is a natural measure of its complexity. We consider low-complexity configurations where the number of distinct D-patterns is at most |D|, the size of the shape. The well-known open Nivat’s conjecture falls in this setting.
We use algebraic tools to study periodicity of such configurations. We show, for example, that a low-complexity configuration must be periodic if it comes from the well-known Ledrappier subshift. In case D is a rectangle – or in fact any convex shape – we establish an algorithm to determine if a given collection of |D| patterns admits any configuration. The result is based on proving that the given patterns admit a periodic configuration if they admit a configuration at all.
Jarkko Kari is a professor of mathematics at the University of Turku in Finland. His research interests include automata theory and the theory of computation, with an emphasis on cellular automata, tilings and symbolic dynamics. He received his PhD from the University of Turku in 1990. From 1996 to 2005, he was an assistant and associate professor at the University Iowa, USA. Jarkko Kari has also been a member of the Finnish Academy of Science and Letters since 2014.
This talk is offered within the framework of the performative event A History of the Domino Problem created by sound artist Michael Winter. The event will be held on the HU campus in Berlin-Mitte and consists of an exhibition in collaboration with Mareike Yin-Yee Lee, a public lecture by Jarkko Kari and a musical pièce played by the Kali Ensemble.
