Open Access

Jörg Lehnert

• Die vorliegende Arbeit beschäftigt sich mit Gruppen von quasi-Automorphismen von Graphen, genauer gesagt, von gefärbten Graphen. Ein gefärbter Graph ist ein Graph, dessen Kantenmenge in eine disjunkte Vereinigung von Mengen von Kanten einer bestimmten Farbe zerlegt ist. Ein Automorphismus eines solchen Graphen muss insbesondere die Farben der Kanten respektieren. Ein quasi-Automorphismus eines solchen Graphen ist eine Bijektion der Eckenmenge auf sich selbst, die nur endlich oft die Autmomorphismeneigenschaft verletzt, d.h. nur endlich viele Kanten nicht respektiert und nur endlich viele Kanten neu entstehen läßt. Die Menge der quasi-Automorphismen eines Graphen bildet eine Untergruppe in der Gruppe der Permutationen der Eckenmenge. Eine Auswahl interessanter Beispiele solcher Gruppen und manche ihrer Eigenschaften sind neben einigen grundsätzlichen Überlegungen Thema dieser Arbeit. Die erste Klasse von Graphen, die wir untersuchen, sind Cayley-Graphen (endlich erzeugter) Gruppen. Dabei werden wir zeigen, dass die quasi-Automorphismengruppe eines Cayley-Graphen nicht von dem (endlichen) Erzeugendensystem abhängt. Wir werden zeigen, dass für eine einendige Gruppe $G$ die quasi-Automorphismengruppe des Cayley-Graphen stets als semidirektes Produkt der finitären Permutationen von $G$ und der Gruppe $G$ selbst zerfällt. In der Klasse der mehrendigen Gruppen gibt es genau $2$ Gruppen für die das ebenfalls gilt, nämlich die Gruppe der ganzen Zahlen ...Z und die unendliche Diedergruppe $D_infty$. In allen anderen Gruppen ist das oben erwähnte semidirekte Produkt stets eine echte Untergruppe. Trotzdem werden wir im Ausblick eine Konstruktion angeben, die für eine gegebene Gruppe $G$ einen Graphen $Gamma$ liefert, dessen quasi-Automorphismengruppe als semidirektes Produkt von $S_Gamma$ -- so bezeichnen wir die Gruppe der finitären Permutationen der Ecken von $Gamma$ -- und $G$ zerfällt. Des Weiteren werden wir die quasi-Automorphismengruppe des ebenen binären Wurzelbaumes betrachten. Wir werden zeigen, dass diese eine Erweiterung von (Richard) Thompsons Gruppe VV durch die Gruppe der finitären Permutationen ist, eine Präsentierung entwickeln und die Endlichkeitseigenschaften dieser Gruppe und einiger Untergruppen beleuchten. Insbesondere werden wir einen Zellkomplex konstruieren, auf dem die Gruppe der quasi-ordnungserhaltenden quasi-Automorphismen, welche das Urbild der Untergruppe FF von VV unter der kanonischen Projektion ist, mit endlichen Stabilisatoren operiert. Diese Operation erfüllt dabei die Bedingungen, die nötig sind, um mit Hilfe von Browns Kriterium nachzuweisen, dass die Gruppe vom Typ FPunendlich ist. Das co-Wort-Problem einer Gruppe $G$ bezüglich eines unter Inversion abgeschlossenen Erzeugendensystems $X$ ist die Sprache aller Worte aus dem freien Monoid $X^*$, die unter der kanonischen Projektion auf ein Element ungleich der Identität in $G$ abgebildet werden. Wir werden zeigen, dass das co-Wort-Problem der quasi-Automorphismengruppe des ebenen binären Wurzelbaumes eine kontext-freie Sprache bildet. Sei $mathop{coCF}$ die Klasse der Gruppen mit kontextfreiem co-Wort-Problem. Diese Klasse ist abgeschlossen bezüglich Untergruppenbildung und alle Gruppen, deren Zugehörigkeit zu $mathop{coCF}$ bisher nachgewiesen wurde, sind Unterguppen der quasi-Automorphismengruppe des ebenen binären Wurzelbaumes. Die $n$-strahligen Houghton-Gruppen erweisen sich als quasi-Automorphismengruppen von Sterngraphen, d.h. von Graphen, die disjunkte Vereinigungen von $n$ Strahlen verschiedener Farben sind. Wir werden uns mit geometrischen Phänomenen der Cayley-Graphen dieser Gruppen beschäftigen. Insbesondere werden wir nachweisen, dass die $2$-strahlige Houghton-Gruppe Houn[2] beliebig tiefe Sackgassen besitzt. Eine Sackgasse der Tiefe $k$ in einem Cayley-Graphen ist ein Element, dessen Abstand zur Identität mindestens so groß ist, wie der Abstand zur Identität aller Elemente im $k$-Ball um das Element. Sogar in einem stärkeren Sinne, der in dieser Arbeit definiert wird, ist die Tiefe der Sackgassen unbeschränkt. Um dies und verwandte Fragen besser behandlen zu können, entwickeln wir Modelle, die eine Beschreibung der Cayley-Graphen von Houn[n] ermöglichen. Im abschließenden Ausblick thematisieren wir einige Ansätze, in denen wir interessante Anwendungen von quasi-Automorphismengruppen sehen.
• This thesis investigates groups of quasi-automorphisms of colored graphs. A graph is colored if its set of edges is a disjoint union of sets of edges of a specific color. An automorphism of such a colored graph respects edges with their colors. A quasi-automorphism of a colored graph is a bijection $f$ of the set of vertices with the property, that both $f$ and its inverse respect all but finitely many colored edges of each color. Thus the set of all quasi-automorphisms of a fixed graph forms a subgroup of the group of all permutations of the set of vertices. The thesis contributes some interesting examples of graphs and the corresponding groups as well as general results on groups of quasi-automorphisms. The first class of graphs dealt with are Cayley-graphs of (finitely generated) groups. We show that the quasi-automorphism group of a Cayley-graph does not depend on the chosen set of generators and that for one-ended groups $G$ the quasi-automorphism group splits as a semidirect product of the group of finitary permutations of $G$ and $G$ itself. Among the groups with more than one end there exist only two groups for which this statement is also true, namely the group of integers and the infinite dihedral group. All other groups contain the semidirect product referred to above as a proper subgroup. We then discuss the group of quasi-automorphisms of the planar rooted binary tree, which is strongly related to Richard Thompson´s group VV. We give a presentation of this group as well as a presentation of a very natural subgroup. We also show that this subgroup is of type FPinfinity by applying Brown´s criterion to a complex which we construct for this purpose. The co-word problem of a group $G$ with respect to the set of generators $X$ (w.l.o.g. closed under inversion) is the language of all words out of $X^*$, which do not represent the identity in $G$. We show that the co-word problem of the group of quasi-automorphisms of the planar rooted binary tree, and therefore of all subgroups of this group, is context-free. All groups which are known to have context-free co-word problem are subgroups of the group of quasi-automorphisms of the planar rooted binary tree. The family of Houghton´s groups can also be regarded as the groups of quasi-automorphisms of certain colored graphs: the graphs given as the disjoint union of $n$ rays, each of a different color. We discuss some geometric phenomena of the Cayley-graphs of these groups, one of them being the existence of so called dead ends and we show that the second of Houghton´s groups has dead ends of arbitrary depth. To deal with this and also some related questions we develop models, which help to understand the Cayley-graphs of Houghton´s groups. Finally we discuss some ideas how to develop the theory of quasi-automorphisms and sketch some possible applications.