imported>FlMcc: /* growthexperiments-addlink-summary-summary:3|0|0 */

2024-12-29T22:22:55Z

growthexperiments-addlink-summary-summary:3|0|0

Neue Seite

[[Datei:Cayley graph of F2.svg|mini|Der Cayleygraph der [[Freie Gruppe|freien Gruppe]] mit zwei Erzeugern ''a'' und ''b'']]

In der [[Mathematik]] ist ein '''Cayleygraph''' ein [[Graph (Graphentheorie)|Graph]], der die Struktur einer (meist [[Endlich erzeugte Gruppe|endlich erzeugten]]) [[Gruppe (Mathematik)|Gruppe]] beschreibt. Er hängt von einer gegebenen, normalerweise endlichen, Menge von [[Erzeugendensystem|Erzeugern der Gruppe]] ab.

[[Arthur Cayley]] hat 1878 als Erster Graphen benutzt, um Gruppen bildlich darzustellen; ein Ansatz, der von [[Max Dehn]] (1911), [[Otto Schreier]] (1927) und anderen weiterentwickelt wurde. Wegen Dehns großer Beiträge wurden Cayleygraphen manchmal auch ''(Dehnsche) Gruppenbilder'' genannt.<ref>Jonathan L. Gross, Thomas W. Tucker: ''Topological graph theory.'' Courier Dover Publications, 2001. ISBN 978-0-486-41741-7. S. 10–14. {{Digitalisat |1=https://books.google.ch/books?id=mrv9OJVdy_cC&hl=de}}</ref> Heute sind Cayleygraphen ein zentrales Werkzeug der [[Geometrische Gruppentheorie|geometrischen Gruppentheorie]].

== Definition ==
Sei <math>G</math> eine [[Gruppe (Mathematik)|Gruppe]] und <math>S</math> ein [[Erzeugendensystem]]. Der Cayleygraph <math>\Gamma=\Gamma(G,S)</math> ist ein [[Färbung (Graphentheorie)|gefärbter]] und [[gerichteter Graph]], der wie folgt konstruiert wird:

* Jedem Element <math>g</math> von <math>G</math> wird ein Knoten zugeordnet: Die Knotenmenge <math>V(\Gamma)</math> von <math>\Gamma</math> wird mit <math>G</math> identifiziert.
* Jedem Erzeuger <math>s</math> aus <math>S</math> wird eine Farbe <math>c_s</math> zugeordnet.
* Für <math>g\in G</math>, <math>s\in S</math>, werden die Knoten, die zu den Elementen <math>g</math> und <math>gs</math> gehören, mit einer gerichteten Kante der Farbe <math>c_s</math> verbunden. Die Kantenmenge <math>E(\Gamma)</math> besteht also aus Paaren der Form <math>(g, gs)</math>, wobei <math>s\in S</math> die Farbe bestimmt.

In der geometrischen Gruppentheorie wird meistens angenommen, dass die Menge <math>S</math> endlich und ''symmetrisch'' sei, das heißt <math>S=S^{-1}</math>, und das Neutralelement der Gruppe nicht enthalte. In diesem Fall ist der Cayleygraph, abgesehen von der Färbung, ein gewöhnlicher Graph: Seine Kanten sind nicht orientiert, und er enthält keine [[Schleife (Graphentheorie)|Schleifen]].

== Beispiele ==
* Sei <math>G=\Z</math> die unendliche [[zyklische Gruppe]] und die Menge <math>S</math> bestehe aus dem Standarderzeuger 1 und seinem Inversen (−1 in additiver Notation). Der zugehörige Cayleygraph ist dann eine unendliche Kette.

* Das Bild ist ähnlich, wenn <math>G=\Z/n\Z</math> die endliche zyklische Gruppe von Ordnung <math>n</math> ist und <math>S</math> wieder aus zwei Elementen besteht, dem Standarderzeuger 1 von <math>G</math> und seinem Inversen; dann ist der Cayleygraph der  [[Zyklischer Graph|n-Zykel]] <math>C_n</math>.

* Der Cayleygraph des [[Direktes Produkt|direkten Produkts]] von Gruppen ist das [[Kartesisches Produkt von Graphen|kartesische Produkt]] der jeweiligen Cayleygraphen. Der Cayleygraph der [[Freie abelsche Gruppe|freien abelschen Gruppe]] <math>\Z^2</math> mit einer Erzeugendenmenge, die aus den vier Elementen <math>(\pm 1,\pm 1)</math> besteht, ist ein unendliches Gitter in der Ebene <math>\R^2</math>, während der Cayleygraph für das direkte Produkt <math>\Z/n\Z\times \Z/m\Z</math> mit analogen Erzeugern ein endliches <math>n\times m</math>-Gitter auf dem [[Torus]] bildet.

[[Datei:Dih 4 Cayley Graph; generators a, b.svg|220px|links|mini|Ein Cayleygraph der Diedergruppe D4]]
[[Datei:Dih 4 Cayley Graph; generators b, c.svg|170px|mini|Anderer Cayleygraph von D4]]
* Der Cayleygraph der [[Diedergruppe]] D4 mit zwei Erzeugern <math>a</math> (90°-Drehung im Uhrzeigersinn) und <math>b</math> (Horizontalspiegelung) ist links dargestellt. Da <math>b</math> sein eigenes Inverses ist, sind die blauen Kanten, die für das Ausführen von <math>b</math> stehen, ungerichtet gezeichnet. Diese Wahl von <math>a</math> und <math>b</math> entspricht der [[Präsentierung einer Gruppe|Präsentierung]]

:: <math> \langle a, b | a^4 = b^2 = e, a b = b a^3 \rangle. \, </math>

* Die Relationen der Gruppe zu dieser Wahl von Erzeugern finden sich im Cayleygraph als [[Zyklus (Graphentheorie)|Zyklen]] wieder, zum Beispiel liefert <math>a^4</math> einen geschlossenen Weg im Graphen, ebenfalls <math>aba^{-3}b</math>.

* Der Cayleygraph der [[Freie Gruppe|freien Gruppe]] mit zwei Erzeugern <math>a</math> und <math>b</math> und der Menge <math>S= \left\{a, b, a^{-1}, b^{-1}\right\}</math> ist oben im Artikel dargestellt, wobei <math>e</math> das Neutralelement bezeichnet. Auf einer Kante nach rechts zu gehen entspricht der Rechtsmultiplikation mit <math>a</math>, während nach oben zu gehen Multiplikation mit <math>b</math> darstellt. Da die freie Gruppe keine Relationen besitzt, enthält dieser Graph keine Zyklen.

== Charakterisierung ==
Die Frage, welche Graphen als Cayleygraphen einer Gruppe <math>G</math> auftreten können, lässt sich wie folgt beantworten:
Die Gruppe <math>G</math> [[Gruppenoperation|wirkt]] durch Linksmultiplikation auf sich selbst (siehe auch [[Satz von Cayley]]). Diese Wirkung liefert auch eine Wirkung von <math>G</math> auf seinem Cayleygraphen. Konkret schickt ein Element <math>h\in G</math> einen Knoten <math>g\in V(\Gamma)</math> auf den Knoten <math>hg\in V(\Gamma)</math>. Die Kantenmenge des Graphen wird durch diese Wirkung respektiert, denn eine Kante <math>(g,gs)</math> wird auf die Kante <math>(hg,hgs)</math> abgebildet. Die Wirkung der Linksmultiplikation irgendeiner Gruppe auf sich selbst ist [[einfach transitiv]]. Dementsprechend ist ein Cayleygraph [[Knotentransitiver Graph|knotentransitiv]]. Dies führt zu der folgenden Charakterisierung von Cayleygraphen:

: ''Ein Graph <math>\Gamma</math> ist ein Cayleygraph einer Gruppe <math>G</math> genau dann, wenn er eine auf den Knoten einfach transitive Wirkung von <math>G</math> durch [[Automorphismus|Automorphismen]] des Graphen (also die Kantenmenge respektierende Abbildungen) zulässt.''

Um die Färbung des Graphen durch die Gruppe <math>G</math> und die Erzeugermenge <math>S</math> zu rekonstruieren, wählt man einen Knoten <math>v_1\in V(\Gamma)</math> aus und beschriftet ihn mit dem Neutralelement der Gruppe. Jeder Knoten <math>v</math> von <math>\Gamma</math> wird dann mit dem eindeutigen Element <math>g</math> von <math>G</math> bezeichnet, das <math>v_1</math> nach <math>v</math> abbildet. Die Menge <math>S</math> von Erzeugern von <math>G</math>, die <math>\Gamma</math> als Cayleygraphen liefert, ist dann die Menge der Beschriftungen der Knoten, die zum ausgewählten Knoten <math>v_1</math> [[adjazent]] sind. Die Erzeugermenge ist genau dann endlich, wenn der Graph lokal endlich ist, also jeder Knoten zu endlich vielen Kanten inzident ist.

Es ist allerdings nicht wahr, dass jeder knotentransitive Graph als Cayleygraph auftritt, und auch sonst beantwortet die obige Aussage natürlich nicht alle Fragen zur Struktur von Cayleygraphen. Beispielsweise ist die Vermutung, dass jeder endliche Cayleygraph einen [[Hamiltonkreis]] enthält, bekannt als [[Lovász-Vermutung]], unbewiesen.

== Einfache Eigenschaften ==
Der Cayleygraph ''Γ''(''G'',''S'') hängt wesentlich von der Wahl der Erzeugermenge ''S'' ab. Wenn ''S'' zum Beispiel ''k'' Elemente hat, so besitzt jeder Knoten von ''Γ'' ''k'' eingehende und ''k'' ausgehende Kanten. Ist ''S'' symmetrisch gewählt, so ist ''Γ'' ein [[regulärer Graph]] von [[Grad (Graphentheorie)|Grad]] ''k''.

Zyklen, das heißt geschlossene Wege, im Cayleygraphen stellen Relationen (siehe [[Präsentierung einer Gruppe]]) zwischen den Elementen von ''S'' dar.

Wenn <math>f \colon G'\to G</math> ein surjektiver [[Gruppenhomomorphismus]] ist, der auf der Erzeugermenge ''S’'' von ''G’'' injektiv ist, dann induziert ''f'' eine [[Überlagerung (Topologie)|Überlagerung]] von Graphen

:: <math> \bar{f} \colon \Gamma(G',S')\to \Gamma(G,S),\quad</math> wobei ''S'' = ''f''(''S’'').

Insbesondere ist dies der Fall, wenn eine Gruppe ''G'' von ''k'' Elementen erzeugt wird, alle von Ordnung ungleich 2, und die Menge ''S'' aus diesen Erzeugern und ihren Inversen besteht. Dann wird der Cayleygraph ''Γ''(''G'',''S'') vom unendlichen regulären [[Baum (Graphentheorie)|Baum]] von Grad 2''k'' überlagert, der zur freien Gruppe über denselben Erzeugern gehört. Ein solcher Baum ist dann eine [[universelle Überlagerung]] des Cayleygraphen und heißt auch Cayleybaum oder [[Bethe-Gitter]].

Auch wenn die Menge ''S'' die Gruppe ''G'' nicht erzeugt, kann ein Graph ''Γ''(''G'',''S'') konstruiert werden. Allerdings wird er nicht [[Zusammenhang von Graphen|zusammenhängend]] sein und wird nicht als Cayleygraph betrachtet. In diesem Fall entspricht jede Zusammenhangskomponente einer [[Nebenklasse (Mathematik)|Nebenklasse]] der Untergruppe, die von ''S'' erzeugt wird.

== Anwendungen in der Gruppentheorie ==
Durch das Studium des Cayleygraphen können Einsichten über die Struktur der Gruppe gewonnen werden. Unter anderem ist es interessant, die [[Adjazenzmatrix]] zu untersuchen, insbesondere mit den Mitteln der [[Spektraltheorie von Graphen]], die geometrische Aussagen, die aus dem
[[Spektrum (Operatortheorie)|Spektrum]] von linearen Operatoren gewonnen werden, in einen [[Diskretheit|diskreten]] Kontext überträgt.

== Geometrische Gruppentheorie ==
Für unendliche Gruppen ist die [[grobe Geometrie]] (''coarse geometry'') des Cayleygraphen, oder seine Äquivalenzklasse bis auf [[Quasi-Isometrie]], fundamental für das Gebiet der [[Geometrische Gruppentheorie|geometrischen Gruppentheorie]]. Für eine [[endlich erzeugte Gruppe]] ist sie unabhängig von der Wahl einer endlichen Menge <math>S</math> von Erzeugern, also eine intrinsische Eigenschaft der Gruppe. Dies ist nur für unendliche Gruppen interessant, da alle endlichen Gruppen – für die <math>S=G</math> gewählt werden kann – quasiisometrisch zu einem Punkt sind.

Der Cayleygraph ist in diesem Zusammenhang ein [[Metrischer Raum|metrisches]] Bild der Gruppe zusammen mit der Wortmetrik, die durch die Wahl der Erzeuger bestimmt wird.

=== Wortmetrik ===
Die Wortmetrik auf dem Cayleygraphen ist gegeben durch die Festlegung, dass alle Kanten des Graphen Länge 1 haben sollen. Äquivalent kann man den Abstand zweier Gruppenelemente <math>g,h</math> definieren als die minimale Anzahl von Faktoren ''aus dem gegebenen Erzeugendensystem'', in die sich <math>gh^{-1}</math> zerlegen lässt, also

:<math> d(g,h) = \min\{n: gh^{-1}=s_1 \dots s_n; s_1, \dots, s_n\in S\}</math>.

Die Wortmetrik hängt (ebenso wie der Cayleygraph selbst) vom Erzeugendensystem <math>S</math> ab. Für verschiedene ''endliche'' Erzeugendensysteme erhält man aber quasi-isometrische (sogar [[Bilipschitz-Äquivalenz|bilipschitz-äquivalente]]) Cayleygraphen. Alle bis auf Quasi-Isometrie bestimmten geometrischen Eigenschaften von Graphen entsprechen also Eigenschaften von Gruppen.

In der geometrischen Gruppentheorie versucht man, algebraische Eigenschaften von Gruppen in geometrische Eigenschaften des Cayleygraphen zu übersetzen. Ein spektakuläres Beispiel dafür ist [[Michail Leonidowitsch Gromow|Gromows]] Satz, dass eine Gruppe genau dann [[Virtuelle Eigenschaft|virtuell]] [[Nilpotente Gruppe|nilpotent]] ist, wenn ihr Cayleygraph polynomielles Volumenwachstum hat, d. h. das Volumen der Bälle vom Radius <math>R</math> durch ein [[Polynom]] in <math>R</math> nach oben begrenzt ist.

=== Wort-hyperbolische Gruppen ===
Eine Gruppe heißt wort-hyperbolisch, wenn ihr Cayleygraph [[δ-hyperbolisch]] für ein <math>\delta > 0</math> ist. Das bedeutet, dass in jedem [[Geodäte|geodätischen]] Dreieck jeder auf einer Kante liegende Punkt Abstand <math>< \delta</math> von mindestens einer der beiden anderen Kanten hat. Diese Definition ist (bis auf den genauen Wert der Konstante <math>\delta</math>) invariant unter Quasi-Isometrie und deshalb unabhängig vom gewählten Erzeugendensystem.

Beispiele wort-hyperbolischer Gruppen sind: [[endliche Gruppe]]n, [[virtuell zyklische Gruppe]]n, endlich erzeugte freie Gruppen, [[Fundamentalgruppe]]n kompakter [[Topologische Fläche|Flächen]] negativer [[Euler-Charakteristik]] und allgemein Fundamentalgruppen kompakter, negativ gekrümmter Mannigfaltigkeiten. In gewisser Weise sind zufällige Gruppen wort-hyperbolisch.<ref>[https://link.springer.com/article/10.1007%2Fs000390300002 Gromov, M. (2003). Random walk in random groups Geometric and Functional Analysis, 13 (1), 73-146]</ref>

=== Rand im Unendlichen ===
Der Cayleygraph hat einen Rand im Unendlichen, formal definiert als die Menge der Äquivalenzklassen geodätischer Strahlen, wobei 2 Strahlen genau dann äquivalent sind, wenn sie endlichen Abstand haben. Die Wirkung der Gruppe auf dem Rand im Unendlichen ist ein „chaotisches“ [[dynamisches System]] und kodiert viele Eigenschaften der Gruppe.

Beispiele: für freie Gruppen ist der Rand im Unendlichen eine [[Cantor-Menge]], für Fundamentalgruppen kompakter negativ gekrümmter <math>n</math>-Mannigfaltigkeiten ist der Rand im Unendlichen eine <math>(n-1)</math>-[[Topologische Sphäre|Sphäre]], für die „meisten“ wort-hyperbolischen Gruppen ist der Rand im Unendlichen aber ein [[Menger-Schwamm]].

== Geschichte ==
Cayley betrachtete die nach ihm benannten Graphen 1878 zunächst nur für endliche Gruppen.<ref>Cayley, A. (1878). The theory of groups: Graphical representation. Amer. J. Math. 1, 174–176. In his Collected Mathematical Papers 10: 403–405.</ref> In seinen unveröffentlichten Notizen zur Gruppentheorie aus den Jahren 1909–10 führte Max Dehn den Cayleygraphen unter dem Namen „Gruppenbild“ ein. Seine Hauptanwendung war die Lösung des [[Wortproblem]]s für die [[Fundamentalgruppe]]n der [[Topologische Fläche|Flächen]] vom Geschlecht ≥ 2 mit geometrischen Methoden, die heute zur Theorie der [[Hyperbolische Gruppe|hyperbolischen Gruppen]] gehören. (Das ist äquivalent zur Lösung des topologischen Problems, welche Kurven in der Fläche sich auf einen Punkt zusammenziehen lassen.) Diese Arbeit war der Beginn der heutigen geometrischen Gruppentheorie.<ref>Dehn, M. (1987). Papers on Group Theory and Topology. New York: Springer-Verlag. Translated from the German and with introductions and an appendix by John Stillwell, and with an appendix by Otto Schreier.</ref>

== Verwandte Konstruktionen ==
Aus einer Präsentierung einer diskreten Gruppe können mehrere den Cayleygraphen verwandte Objekte gebildet werden.

=== Cayleykomplexe ===
Der '''Cayleykomplex''' ist eine dem Cayleygraphen sehr ähnliche Konstruktion. Er ist ein [[Zellkomplex]], der den Cayleygraphen als [[N-Skelett|1-Skelett]] besitzt, in den aber zusätzlich 2-Zellen eingeklebt werden. Für die 2-Zellen wird neben der Gruppe <math>G</math> und der Erzeugendenmenge <math>S</math> auch eine Wahl von Relationen <math>R</math> benötigt, so dass <math>(S,R)</math> eine [[Präsentation einer Gruppe|Präsentierung]] von <math>G</math> ist. Jede Relation in <math>R</math> liefert für jeden Knoten im Cayleygraphen einen Zykel, entlang dem jeweils eine 2-Zelle eingeklebt wird.

Der Cayleykomplex der Gruppe '''Z'''2 mit der Präsentierung <math>\langle \alpha, \beta \mid \alpha\beta\alpha^{-1}\beta^{-1} = e \rangle</math> ist zum Beispiel eine Pflasterung der Ebene mit Einheitsquadraten, deren 1-Skelett der oben beschriebene Cayleygraph von '''Z'''2 ist.

=== Schreiergraphen ===
Wenn als Knoten anstelle von Elementen der Gruppe <math>G</math> Rechtsnebenklassen einer festen Untergruppe <math>H\subset G</math> gewählt werden, erhält man eine verwandte Konstruktion, den [[Schreiergraph]]en <math>\Sigma(G,H,S)</math>, wobei <math>S</math> wieder eine Erzeugermenge von <math>G</math> ist. Ist <math>H</math> die [[Triviale Gruppe|triviale Untergruppe]], so ist <math>\Sigma(G,H,S)</math> einfach wieder der Cayleygraph <math>\Gamma(G,S)</math>.

== Einzelnachweise ==
<references />

[[Kategorie:Regulärer Graph]]
[[Kategorie:Geometrische Gruppentheorie]]
[[Kategorie:Gerichteter Graph]]

Cayleygraph - Versionsgeschichte

imported>FlMcc: /* growthexperiments-addlink-summary-summary:3|0|0 */