Dokument: Einige Algorithmische Probleme über Automorphismen von freien Gruppen

Titel:	Einige Algorithmische Probleme über Automorphismen von freien Gruppen
Weiterer Titel:	Some algorithmic problems about automorphisms of free groups
URL für Lesezeichen:	https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=39041
URN (NBN):	urn:nbn:de:hbz:061-20160725-090640-8
Kollektion:	Dissertationen
Sprache:	Deutsch
Dokumententyp:	Wissenschaftliche Abschlussarbeiten » Dissertation
Medientyp:	Text
Autor:	Dip.-Math. Leßmann, Thomas [Autor]
Dateien:	[Dateien anzeigen] Adobe PDF [Details] 945,7 KB in einer Datei [ZIP-Datei erzeugen] Dateien vom 22.07.2016 / geändert 22.07.2016
Beitragende:	Priv.-Doz. Prof. Dr. Bogopolski, Oleg [Betreuer/Doktorvater] Prof. Dr. Singhof, Wilhelm [Gutachter]
Dewey Dezimal-Klassifikation:	500 Naturwissenschaften und Mathematik » 510 Mathematik
Beschreibungen:	Im ersten Kapitel entwickeln wir einen elementaren Algorithmus, mit dem sich für zwei endlich erzeugte Untergruppen $U,H$ der freien Gruppe $F_2$ entscheiden lässt, ob es einen Automorphismus $\alpha:F_2\ra F_2$ mit $\alpha(U)\leqslant H$ gibt. Ein nicht-elementarer Algorithmus ist in einem Artikel von P. Silva und P. Weil zu finden. Für den Fall, dass $U$ zyklisch ist, wird dieses Problem im gleichen Artikel ebenfalls elementar gelöst, wobei unsere Lösung effizienter ist. In den weiteren Kapiteln untersuchen wir die Nielsenwege einer Homotopieäquivalenz $f:\Gamma\rightarrow\Gamma$ auf einem endlichen Graphen $\Gamma$ (dies sind Wege, die nach Anwendung von $f$ und anschließender Reduktion unverändert bleiben). Die Nielsenwege lassen sich hierbei nach E. C. Turner durch einen von ihm und R. Z. Goldstein eingeführten Überlagerungsgraphen $D_f$ beschreiben: Die Projektion eines reduzierten Weges zwischen zwei der endlich vielen "toten" Punkte in $D_f$ ist ein Nielsenweg und jeder Nielsenweg entsteht eindeutig auf diese Weise. Zur Untersuchung von Wegen in $D_f$ sind sogenannte bevorzugte Kanten entscheidend, welche ebenfalls von R. Z. Goldstein und E. C. Turner definiert werden. Diese erfüllen die folgende bekannte Eigenschaft: Für einen reduzierten Weg $\gamma$ in $D_f$, dessen Projektion ein irreduzibler Nielsenweg ist, gibt es eine Zerlegung $\gamma=\gamma_1\gamma_2$, so dass die Kanten von $\gamma_1$ und von $\ol{\gamma_2}$ jeweils ab der zweiten Kante bevorzugt sind. Für den obigen Weg $\gamma=\gamma_1\gamma_2$ erhalten wir dann eine explizite und nur von $f$ abhängige obere Schranke für die Länge des Schnittpunktes von $\gamma_1$ und $\ol{\gamma_2}$ (die Knoten in $D_f$ sind bestimmte Wege in $\Gamma$). Hierauf aufbauend konstruieren wir einen Graphen, welcher die irreduziblen Nielsenwege von $f$ beschreibt. Wir werden zeigen, dass diese Konstruktion algorithmisch durchgeführt werden kann, falls $f:\Gamma\rightarrow\Gamma$ eine relative Train-Track Abbildung ist. Wir erklären außerdem, wie die hierbei entwickelten Techniken benutzt werden können, um einige Schritte des Algorithmus von O. Bogopolski und O. Maslakova zur Berechnung von Fix$(\alpha)$ für einen Automorphismus $\alpha$ von $F_n$ effizienter zu machen. Zusätzlich finden wir für relative Train-Track Abbildungen eine neue obere Schranke für die Länge von irreduziblen Nielsenwegen exponentieller Höhe. In the first chapter, we develop an elementary algorithm that decides, given two finitely generated subgroups $U$ and $H$ of the free group $F_2$, whether or not there is an automorphism $\alpha:F_2\rightarrow F_2$ such that $\alpha(U)\leqslant H$. We note that another more complicated algorithm was given by P. Silva und P. Weil. For the special case, when $U$ is cyclic, the authors also solved the problem elementary. In this particular case the solution presented here is more efficient. In the remaining two chapters, we investigate the Nielsen paths of a homotopy equivalence $f:\Gamma\rightarrow\Gamma$ on a finite graph $\Gamma$ (up to reductions, these are the paths that are invariant under $f$). By E. C. Turner, the Nielsen paths of $f$ can be described through the covering graph $D_f$ introduced by him and R. Z. Goldstein. The projection of any reduced path between two of the finitely many `dead' points in $D_f$ is a Nielsen path, and every Nielsen path can be uniquely obtained in this way. For the study of paths in $D_f$, the so-called preferable edges play a crucial role. These edges were also defined by R. Z. Goldstein and E. C. Turner. They satisfy the following known property: For a reduced path $\gamma$ in $D_f $ whose projection is an irreducible Nielsen path, there is a decomposition $\gamma =\gamma_1\gamma_2$ so that all edges of $ \gamma_1$ and $\ol{\gamma_2}$ are preferable except for the first edge of each path. For the path $\gamma=\gamma_1\gamma_2$ written above, we get an explicit upper bound in terms of $f$ for the length of the point, where $\gamma_1$ and $\ol{\gamma_2}$ meet (note that the vertices of $D_f$ are certain paths in $\Gamma$). Following this way, we construct a graph that represents the irreducible Nielsen paths of $f$. We show that this construction can be carried out algorithmically if $f$ is a relative train track map. We also explain how one can use the developed techniques in order to make more efficient some steps of O. Bogopolski's and O. Maslakova's algorithm for finding the fixed point set of an automorphism $\alpha$ of $F_n$. Finally, we find a new upper bound for the length of irreducible Nielsen paths of exponential height for a relative train track map.
Lizenz:	Urheberrechtsschutz
Fachbereich / Einrichtung:	Mathematisch- Naturwissenschaftliche Fakultät » WE Mathematik » Algebra und Zahlentheorie
Dokument erstellt am:	25.07.2016
Dateien geändert am:	25.07.2016
Promotionsantrag am:	31.05.2016
Datum der Promotion:	19.07.2016