Contributions to the Domino Problem: Seeding, Recurrence and Satisfiability [Slides] STACS 2024, Clermont-Ferrand, March 2024
We study the seeded domino problem, the recurring domino problem and the \(k\)-SAT problem on finitely generated groups. These problems are generalization of their original versions on \(\mathbb{Z}^2\) that were shown to be undecidable using the domino problem. We show that the seeded and recurring domino problems on a group are invariant under changes in the generating set, are many-one reduced from the respective problems on subgroups, and are positive equivalent to the problems on finite index subgroups. This leads to showing that the recurring domino problem is decidable for free groups. Coupled with the invariance properties, we conjecture that the only groups in which the seeded and recurring domino problems are decidable are virtually free groups. In the case of the \(k\)-SAT problem, we introduce a new generalization that is compatible with decision problems on finitely generated groups. We show that the subgroup membership problem many-one reduces to the \(2\)-SAT problem, that in certain cases the \(k\)-SAT problem many one reduces to the domino problem, and finally that the domino problem reduces to \(3\)-SAT for the class of scalable groups.
Snakes, SAWs and Symbolic Dynamics [Slides] Complexity of Simple Dynamical Systems in honor of Jarkko Kari's 60th birthday, CIRM, February 2024
TODO
Substitutions and Hierarchical Structures on Countable Groups Research School in Discrete Mathematics and Computer Science, CIRM, February 2024
In this talk, we will show how we can expand the notion of substitutions to countable groups. We begin by looking at the class of ccc groups. Groups in this class admit hierarchical decompositions that allow for the definition of substitutions and substitutive subshifts. We then show these substitutions may define minimal and/or uniquely ergodic shifts under different combinatorial properties. At the end, we will briefly look at how to expand our definition to larger classes of groups. Joint work with Christopher Cabezas and Pierre Guillon.
Caminos Autoevitantes desde la Dinámica Simbólica XCI Encuentro Anual de la Sociedad de Matemática de Chile, December 2023
Los caminos autoevitantes sobre redes infinitas fueron introducidos por P. Flory en los años 50 como una herramienta para el estudio de polímeros de cadena larga. Desde entonces su comportamiento crítico y propiedades de transición de fase han atraído la atención tanto de físicos como matemáticos. Hoy en día los caminos autoevitantes se estudian en grafos cuasi-transitivos localmente finitos a través de herramientas de combinatoria, probabilidades y mecánica estadística. En esta charla, estudiaremos el conjunto de los caminos autoevitantes bi-infinitos en grafos de Cayley de grupos finitamente generados, llamado el esqueleto del grupo, usando la perspectiva de la dinámica simbólica para entender como las propiedades algebraicas y geométricas del grupo subyacente influencian las propiedades dinámicas y computacionales del esqueleto. Trabajo en conjunto con Nathalie Aubrun.
Séminaire des Mathématiques Discrètes, U. Liège, September 2023, [Slides]
Domino Snake Problems were introduced in 1979 by Myers, as an a priori simpler variants of the now famous Domino Problem. Among these problems the infinite snake problem stands out. It asks, given a set of tiles and adjacency rules, if there exists a tiling of a bi-infinite simple path on the discrete plain that respects adjacency rules locally. This problem was shown to be undecidable in 2002 by Adleman et al. through the use of a tiling that cleverly code Hilbert's space filling curve. In this presentation, we will take a brief look at what happens when we change the underlying structure of the problem to a different Cayley graph and what happens when we place additional constraints on the path the snakes are allowed to take. This is joint work with Nathalie Aubrun.
Subshifts de Tipo Finito Aperiódicos Para Grupos de Bausmlag-Solitar Generalizados Seminario de Sistemas Dinámicos de Santiago, August 2023
En esta presentación estudiaremos construcciones de subshifts de tipo finito (SFTs) aperiódicos en grupos de Baumslag-Solitar generalizados; una clase de grupos bien estudiada que contiene los grupos de Baumslag-Solitar y los grupos de nudos tóricos. La demostración esta basada en un teorema de clasificación de Whyte y dos construcciones de SFTs aperiódicos en \(\mathbb{F}_n\times\mathbb{Z}\) y \(BS(m,n)\). Estas construcciones utilizan la técnica de "doblar-caminos" para levantar configuraciones aperiódicas de \(\mathbb{Z}^2\) y el plano hiperbólico en \(\mathbb{F}_n\times\mathbb{Z}\) y \(BS(m,n)\) respectivamente. Este trabajo es en conjunto con Nathalie Aubrun y Sacha Huriot-Tattergrain.
El Problema de Dominó y Aperiodicidad en grupos
Seminario 'Compartamos lo que sabemos de grupos', Universidad de Chile, August 2023
Coloquio DMCC, USACH, August 2023
Dado un conjunto finito de colores y un número finito de patrones prohibidos, ¿existe un algoritmo que determina si se puede colorear el plano discreto sin crear un patrón prohibido? Esta pregunta, mejor conocida como el problema del dominó, fue resuelta en los años 60 por Berger, quien mostró que con un número finito de patrones prohibidos se pueden crear coloreos aperiódicos e incluso simular máquinas de Turing. Pero, ¿qué sucede cuando cambiamos la geometría subyacente? En esta charla exploraremos qué cambia cuando reemplazamos el plano discreto por el grafo de Cayley de otro grupo: cómo las propiedades algebraicas y geométricas del grupo subyacente influencian las propiedades de los coloreos. Veremos además el estado del arte de los problemas de dominó y aperiodicidad.
Realizability of Subgroups by SFTs Journées SDA2, March 2023
Strongly aperiodic (SA) SFTs have been an object of interest ever since the proof of the undecidability of Domino Problem by Berger in 1962. Since then, numerous finitely generated groups have been shown to admit SA SFTs, as well as obstructions to their existence. Viewed from a different angle, these SFTs can be seen as subshifts in which every stabilizer is the trivial subgroup. Can this be done for other subgroups ? Given a subgroup H, does there exist a SFT such that all stabilizers are H ? What sets of subgroups can appear as the set of stabilizers of some SFT ? In this talk we will explore these questions and introduce some dynamical, algebraic and computational restrictions to the realizability of these sets.
The Domino Snake Problem
Journées de l'ANR C_SyDySi, Orléans
Séminaire GALaC, LISN, Gif-sur-Yvette, March 2023
Deep within the swamp of undecidability lies the elusive domino snake. This species, first discovered in the 1970s by Myers, was originally introduced as an a priori simpler problem than the now celebrated Domino Problem. In this talk we will take a tour through what is known about this species, looking at its different variants: the infinite snake problem, the snake rechability problem and the ouroboros problem. We will also see how the infinite snake problem can be reduced to a problem in one-dimensional symbolic dynamics.
Symbolic Dynamics on Groups: Emptiness and Aperiodicity
Séminaire Doctorante LAMFA, Amiens
Séminaire DGeCo, IMJ-PRG Paris, January 2023
Tilings of the plane or infinite grid have been a rich field of study for many years. Through tiling with local rules, it is even possible to create aperiodicity and embed computation in the plane. But what happens when we begin changing the underlying structure? We will explore how different underlying groups and their geometries influence what we can obtain through the use of local rules and take a look at the state of the art of the problems of emptiness and aperiodicity.
Strongly Aperiodic SFTs on Generalized Bausmlag-Solitar groups [Slides]
Séminaire SymPA, LAMFA, Amiens, October 2022
Journées SDA2 2022, Liege, June 2022
We look at constructions of aperiodic SFTs on generalized Baumslag-Solitar (GBS) groups, a well-studied class of groups that includes Baumslag-Solitar groups and Torus Knot groups. Our proof is based on a structural theorem by Whyte and two constructions of strongly aperiodic SFTs on \(\mathbb{F}_n\times\mathbb{Z}\) and \(BS(m,n)\) of our own. These constructions rely on a path-folding technique that lifts an SFT on \(\mathbb{Z}^2\) inside an SFT on \(\mathbb{F}_n\times\mathbb{Z}\) and an SFT on the hyperbolic plane inside an SFT on \(BS(m,n)\). In the former case, the path folding technique also preserves minimality. Joint work with Nathalie Aubrun and Sacha Huriot.
Le Problème de l'Ange sur les Groupes Rencontre autour des systèmes dynamiques (Porquerolles), June 2022