Graph Subshifts

Amélia Durbec (1)

1 LIS - Laboratoire d'Informatique et des Systèmes (LIS) (Marseille, Toulon)

We propose a definition of graph subshifts of finite type that extends the power of both subshifts of finite type from classical symbolic dynamics and finitely presented groups from combinatorial group theory. These are sets of (finite or infinite) graphs that are defined by forbidding finitely many local patterns. The definition makes it not obvious to forbid finite graphs, but we prove that some nontrivial subshifts actually contain only infinite graphs: these are built either by forcing aperiodicity (such as in classical constructions of subshifts of finite type on the grid), or no residual finiteness of the period group.

Domains: Dynamical Systems [math.DS]; Discrete Mathematics [cs.DM]; Combinatorics [math.CO]

Amélia Durbec. Graph Subshifts. 27th International Workshop on Cellular Automata and Discrete Complex Systems, Jul 2021, Marseille, France. ⟨hal-03238087v2⟩