Hom shifts are a family of simple two-dimensional subshifts (rules for colourings of the grid Z^2) that look the same in every direction, i.e. invariant by rotation and symmetry. This restriction breaks classical methods for embedding computation in subshifts, and problems that are undecidable in general seem to become tractable, and can usually be restated in terms of graphs. This talk is about gluing distance in Hom shifts: given two n x n admissible partial colourings, how far do they need to be so that we can glue them together in a larger colouring ? It turns out that the problem can be restated in terms of homomorphism reconfiguration in graph theory, and the proofs rely on some kind of path transformations in graphs that can be intuitively seen as homotopies, making a link with algebraic topology in graphs. On every simple example, this distance is constant or linear; however, we produce a more elaborate example with logarithmic gluing distance. We conjecture that constant, linear and logarithmic distances are the only three possible behaviours, and that this makes an argument for these behaviours to be "combinatorially natural" for general subshifts (in the absence of computation).
This is a joint work with Silvère Gangloff and Piotr Opocha.