Le groupegroupes, ou (groupe)²s est un sous-groupe du groupe de travail Pythéas Fogg s’intéressant aux questions de pavages de groupes. Les deux points centraux de toutes ces questions sont:

la (les) périodicité dans les pavages de groupe
le problème du domino

Pour être tenu au courant des nouvelles à propos du groupegroupes: la liste de diffusion: https://listes.math.cnrs.fr/wws/info/groupegroupes, ou contacter Etienne Moutot <etienne(DOT)moutot[AT]math(DOT)cnrs(DOT)fr>

Rencontres à venir:

Rencontres passées

26/02/2021: Solène Esnay

la preuve de Cohen de non forte apériodicité pour ∞ ends

classification de Stallings : un groupe a

0 bout ss'il est fini
2 bouts ss'il est virtuellement ℤ
∞ bouts ss'il est obtenu par produit libre ou HNN-extension (éventuellement avec amalgamations)
1 bout dans tous les autres cas.

groupe avec DP indécidable, un SFT faiblement apériodique mais pas de SFT fortement apériodique (mais avec sous-groupe admettant un SFT fortement apériodique) :

 tous les produits libres de deux groupes infinis dont un a DP indécidable (comme ℤ²).

ℤ² → on pensait avoir un preuve, mais en fait peut être pas…

Recollage périodique de Piantadosi selon les lignes de ℤ de ℤ²*ℤ Début de contre-exemple ? Pavage de ℤ² apériodique ternaire dont les 3 lettres apparaissent dans toutes les configurations. Règles vertiales: ..0000000122222.. qui cassent les périodent "verticales pures". représentation par arbres de Basse-Serre ?

BS(m,n)
Lamplighter group

19/03/2021: Guilhem Gamard

Liens MSO / sous-shifts de Törmä (et Jeandel-Theyssier)

Question de Guilhem : pour toute formule et tout degré maximal, il existe un jeu de tuiles tel que tout graphe est pavable ss'il satisfait la formule ou le contraire ?

11/06/2021: Guillaume Theyssier

Indécidabilité de MSO en largeur arborescente infinie de Kuske-Lohrey

Slides: http://pytheas.math.cnrs.fr/pmwiki/uploads/PytheasFogg/GroupeGroupes/MSO_guillaume.pdf

La clé se trouve dans le livre de le livre de Courcelle et Engelfriet: https://hal.archives-ouvertes.fr/hal-00646514/document

Remarques de la séance:

Existe-t-il un graphe avec mineurs grilles arbitrairement grands mais DP / DP initialisé décidable ?
oui DP en non connexe : union de tores de taille 2ⁿ×2ⁿ.
oui DP en connexe : cylindres de diamètre 2ⁿ de longueur surexponentielle en 2ⁿ collés chacun (sauf les plus petits) à deux plus petits à sa gauche.
DP initialisé indécidable sur les deux cas, par réduction de l'arrêt.
Considérer la classe des graphes avec des mineurs grilles arbitrairement grands pouvant être obtenus par contractions à distance bornée.

02/07/2021: Nicolás Bitar

Les simulations dans le LampLighter de Salo-Bartholdi pour essayer de dessiner des grilles arbitrairement grandes

03/12/2021: Samuel Petite

Directions de déterminisme dans les sous-shifts de groupes. Présentation de résultats non publiés autour de la définition de "directions" d'expansivité pour des actions de groupes.

15/12/2021: Benjamin Hellouin

Première journée: conditions de pavages des groupes moyennables avec un jeu de tuiles fixé.

Tableau 1 Tableau 2 Tableau 3

16/12/2021: Toujours Benjamin Hellouin (en présence de Pascal Vanier)

Problème du Domino Apériodique

18/02/2022: Discussions autour des pavages de groupes, de graphes et MSO.

Trucs intéressants à lire

Greenfeld-Tao 2
BS, HNN extensions et substitutions : Inviter Eduardo Silva
DP sur les groupes à un relateur: Solène
Liens avec MSO : S’intéresser aux graphes sommet-transitifs
Groupes d'automates (flou mais ça serait cool)
Est-ce que certaines propriétés de graphe similaire à la tree-width (clique-width ?) pourraient nous donner une preuve de DP indécidable ? (Demander à Jérémie)
La simulation de Barbieri sur les produits → Sebastián

   Est-ce que ça s'applique à une classe de groupes d'automates ?

la preuve de Jeandel de décidabilité du problème du mot à partir de SFT fortement apériodique / notion de distingablement apériodique → Jérémie
brambles de Kreutzer-Tazari
Robertson-Seymour : lien polynomial entre tree-width et taille de grille mineure
Groupes d'automates et groupes automatiques de Bartholdi-Silva

   La structure combinatoire de ces groupes permet-elle des constructions ?

Questions initiales

Question 0 : undecidable DP ⇔ non virtuellement libre ?

Par Kuske-Lohrey, cela ferait de DP une sorte de problème universel pour MSO, de même que WP est universel pour FO. Connaît-on un graphe régulier qui a MSO indécidable mais DP (pointé) décidable ?

Question 1 : ∃ strongly aperiodic SFT ⇔ 1 end and cocomputably enumerable WP ?

Est-ce que ça aiderait de sortir des groupes et de parler de graphes ?

Question 1.1: Est-ce que si aucun SFT de G n'est fortement apériodique, alors il existe une direction t.q. chaque SFT contient une configuration faiblement périodique dans cette direction ?
Question 1.2: Est-ce qu'on peut en déduire qu'il existe des élements n-axiaux sur cette direction ? (ce qui impliquerait que G a au moins 2 bouts)

(mais quelque part on doit faire intervenir la décidabilité du problème du mot)

Question 2 : ∃ weakly aperiodic SFT ⇔ not virtually ℤ ?

On peut décortiquer en 3 cas (par ordre de difficulté ?) : ∞ ends / WP decidable / 1 end and undecidable WP (exemples : groupes admettant un sous-groupe 1 end and decidable WP. d'autres ?).

Question 3 : ∃ weakly not strongly aperiodic SFT ⇔ not virtually ℤ and not virtually ℤ² ?

Est-ce qu'on peut trouver un contre-exemple ?