Recent Changes - Search:

edit SideBar

QuestionsDePavagesDeGroupe

  • 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é) ? 
   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-LohreyGuillaume
   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.
Edit - History - Print - Recent Changes - Search
Page last modified on 11 June 2021 à 16h57