• View
• Edit
• History
• Print

QuestionsDePavagesDeGroupe

! Cette page est une vieille page, qui n'est plus mise à jour !

Nouvelle page: GroupeGroupes

• 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 decidable 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 ℤ² ?

   Contre-exemple ?

• Si une configuration d'un SFT faiblement apériodique a un stabilisateur distingué, alors le quotient admet un SFT fortement apériodique.

   La distingaison est cruciale : de nombreux groupes (par exemple virtuellement libres, ou peut-être sans sous-groupe finiment engendré avec decidable WP) admettant des SFT faiblement apériodiques n'ont pas de sous-groupe admettant des SFT fortement apériodiques.

• Est-ce qu'il y a des groupes où l'indécidabilité de DP pointé (ou l'existence de SFT fortement apériodique) est plus facile à montrer que DP normal ?

À lire :

• la preuve de Cohen de non forte apériodicité pour ∞ ends → Julien E. 26.02.2021

    Soucis dans la preuve de Cohen: https://mathoverflow.net/questions/341989/existence-of-n-axial-elements-in-groups-with-at-least-2-ends/341993#341993
   Pourrait-elle aider pour des résultats d'AC sur 𝔽₂ (nilrigidité, quasi-équicontinuité) ? 

• liens MSO / sous-shifts de Törmä (et Jeandel-Theyssier) → Guilhem 12 ou 19 mars

   Question 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 ?

• l'indécidabilité de MSO en largeur arborescente infinie de Kuske-Lohrey → Guillaume

   Est-ce que qu'on peut reformuler sous forme de problème de pavage ?

• La simulation de Barbieri sur les produits → Sebastián

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

• les simulations dans le LampLighter de Salo-Bartholdi pour essayer de dessiner des grilles arbitrairement grandes → Nicolás
• 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 ?

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

Séance du 11/06/2021 :

• 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.