
Evènement pour le groupe Graphes et Logique
Date  20110329 11:0012:00 
Titre  Contextfree groups and locally finite graphs of finite treewidth 
Résumé  A finitely generated group G is called contextfree, if the set of words which represent the identity in G (over its generators) forms a contextfree language. It is easy to see that this property is an invariant of the group and does not depend on the choice of generators. Muller and Schupp proved in 1983 that a group G is contextfree if and only if it is virtually free, i.e., it has a free subgroup of finite index. Over the past decades many other characterizations of contextfree groups have been established. For example, by an action on trees with finite node stabilizers (Dicks 1980, Dicks and Dunwoody 1989), decidability of the MSO theory of its Cayley graph (Kuske and Lohrey 2005). A related theorem of Kuske and Lohrey characterizes contextfree groups by Cayley graphs of finite treewidth.
Actually, we can state the following result:
Let Γ be a connected and locally finite graph of finite treewidth. Let G be a group acting on Γ with finitely many orbits. Assume that each nodestabilizer is finite. Then G is virtually free.
In my talk I will speak about a direct and combinatorial proof of this result which became possible due to a modification of a recent construction of Krön for a combinatorial proof of a structure theorem of Stallings (used in all other proofs for the theorem of Muller and Schupp). The talk is based on a joint work with Armin Weiß. 
Lieu  salle 76 
Orateur  Volker Diekert 
Email  volker.diekert@fmi.unistuttgart.de 
Url  FMI, Stuttgart university 
Aucun document lié à cet événement. RetourRetour à l'index
 