Narrow Results

We describe an algorithm that computes the index of a finitely generated subgroup in a finitely L-presented group provided that this index is finite. This algorithm shows that the subgroup membership problem for finite index subgroups in a finitely L-presented group is decidable. As an application, we consider the low-index subgroups of some self-similar groups including the Grigorchuk group, the twisted twin of the Grigorchuk group, the Grigorchuk super-group, and the Hanoi 3-group.

In this paper we prove that the profinite completion of the Grigorchuk group is not finitely presented as a profinite group. We obtain this result by showing that is infinite dimensional. Also several results are proven about the finite quotients including minimal presentations and Schur Multipliers.

L systems generalize context-free grammars by incorporating parallel rewriting, and generate languages such as EDT0L and ET0L that are strictly contained in the class of indexed languages. In this paper, we show that many of the languages naturally appearing in group theory, and that were known to be indexed or context-sensitive, are in fact ET0L and in many cases EDT0L. For instance, the language of primitives and bases in the free group on two generators, the Bridson–Gilman normal forms for the fundamental groups of 3-manifolds or orbifolds, and the co-word problem of Grigorchuk’s group can be generated by L systems. To complement the result on primitives in rank 2 free groups, we show that the language of primitives, and primitive sets, in free groups of rank higher than two is context-sensitive. We also show the existence of EDT0L languages of intermediate growth.

We prove that the conjugacy problem in the first Grigorchuk group $\mathrm{\Gamma }$ can be solved in linear time. Furthermore, the problem to decide if a list of elements $w_1,\dots ,w_k\in \mathrm{\Gamma }$ contains a pair of conjugate elements can be solved in linear time. We also show that a conjugator for a pair of conjugate element $u,v\in \mathrm{\Gamma }$ can be found in polynomial time.

The following sections are included:

• Introduction
• Polya’s Recurrence Theorem
• Burnside’s Problem
• Conclusion
• Bibliography

We study the Tutte polynomial of two infinite families of finite graphs. These are the Schreier graphs associated with the action of two well-known self-similar groups acting on the binary rooted tree by automorphisms: the first Grigorchuk group of intermediate growth, and the iterated monodromy group of the complex polynomial z² - 1 known as the Basilica group. For both of them, we describe the Tutte polynomial and we compute several special evaluations of it, giving further information about the combinatorial structure of these graphs.