Subshifts of Finite Type on Groups : Emptiness and Aperiodicity

Sous-décalages de type fini sur des groupes : problèmes du vide et d'apériodicité Un sous-décalage de type fini est un ensemble de pavages d'un groupe sujet à un nombre fini de contraintes locales, où le groupe agit par translation. Ces dernières années, de nombreux progrès ont été réalisés dans la compréhension de leurs propriétés dynamiques et calculatoires. Le but de cette thèse est de poursuivre cette étude sur la manière dont les propriétés algébriques et géométriques du groupe sous-jacent influencent les propriétés des sous-décalages de type fini définis sur le groupe. Les résultats sont regroupés en trois grandes catégories : décidabilité, apériodicité et substitutions. Dans la première partie, nous étudions le problème du domino, ses variantes, et les conséquences de son indécidabilité sur de nombreux groupes de type fini. Nous classifions la calculabilité du Problème du Domino à Première Tuile Fixée, du Problème du Domino Récurrent, du Problème k-SAT, et des Problèmes du Domino Serpent pour de nombreuses classes de groupes bien connues. En particulier, ils sont tous décidables pour des groupes virtuellement libres. Cette classification est obtenue par des réductions utilisant des constructions SFT, la théorie des automates, et la logique monadique du second ordre. A la fin de la première partie, nous prenons une tangente pour étudier l'ensemble des marches auto-évitantes bi-infinies sur les graphes de Cayley. Cet ensemble apparaît naturellement dans l'étude du problème du serpent infini et est un sous-décalage de ℤ. Nous classifions les groupes pour lesquels ce sous-décalage est apériodique, de type fini, et sofique. Nous étudions également son entropie et sa relation avec la constante connective du graphe de Cayley. La deuxième partie traite de l'existence de sous-décalages de type fini fortement et faiblement apériodiques. Nous commençons par une étude de l'état de l'art de ces problèmes et explorons les parallèles avec des problèmes de probabilité et de combinatoire. Nous examinons ensuite quels sous-groupes d'un groupe peuvent être réalisés en tant que stabilisateurs de sous-décalages de type fini, en établissant des conditions algébriques et calculatoires pour que cela se produise. Dans ce même cadre, nous introduisons la classe des groupes périodiquement rigides, c'est-à-dire des groupes où chaque sous-décalage de type fini faiblement apériodique est fortement apériodique. Nous terminons cette partie en construisant, à partir des travaux d'Aubrun et de Kari, les premiers exemples de sous-décalages de type fini fortement apériodiques sur des groupes de Baumslag-Solitar non résolubles et sur Fₙ x ℤ. Par des théorèmes de Whyte et Cohen, nous obtenons l'existence de tels sous-décalages pour les groupes de Baumslag-Solitar généralisés non cycliques. La dernière partie de cette thèse introduit de nouvelles notions de substitutions, de systèmes S-adiques, et leurs sous-décalages correspondants pour les groupes dénombrables. Nous identifions trois classes de groupes. Premièrement, nous définissons les groupes S-décomposables. Ces groupes ont la structure hiérarchique appropriée pour définir des systèmes S-adiques généraux. Deuxièmement, nous étudions les groupes ccc introduits par Gao, Jackson et Seward, car ils permettent de définir des systèmes S-adiques à forme constante. Troisièmement, nous introduisons les groupes monoformes. Ces groupes permettent de définir des substitutions à forme constante. Nous fournissons des exemples pour les trois classes et des exemples pour leurs systèmes S-adiques correspondants. Nous terminons par l'étude des propriétés dynamiques des sous-décalages définis par ces systèmes. Nous montrons qu'en général, ils sont minimaux sous des conditions de primitivité, et que pour certains groupes ccc moyennables, ils ont une entropie nulle et sont uniquement ergodiques.