Cayley-graaf

In de wiskunde is een Cayley-graaf een gerichte graaf die de structuur van een groep, meestal een eindige, in beeld brengt. De Cayley-graaf hangt af van een, meestal eindig, aantal voortbrengers van de groep.

De Engelse wiskundige Arthur Cayley maakte in 1878 als eerste gebruik van grafen om groepen aanschouwelijk voor te stellen. Dit idee werd door Max Dehn (1911), Otto Schreier (1927) en anderen verder ontwikkeld. Vanwege de grote bijdrage van Dehn wordt een Cayley-graaf ook wel met de door Dehn bedachte naam (Dehnse) groependiagram aangeduid.^[1] Tegenwoordig zijn Cayley-grafen een belangrijk hulpmiddel in de meetkundige groepentheorie.

Gegeven zijn een groep ${\displaystyle G}$ en een systeem ${\displaystyle S\subset G}$ van voortbrengers van ${\displaystyle G}$. De Cayley-graaf ${\displaystyle \Gamma =\Gamma (G,S)}$ van het paar ${\displaystyle (G,S)}$ is een gekleurde en gerichte graaf die als volgt is opgebouwd:

• Aan elk element ${\displaystyle g\in G}$ wordt een knoop toegewezen. De verzameling knopen ${\displaystyle V(\Gamma )}$ van ${\displaystyle \Gamma }$ wordt met ${\displaystyle G}$ geïdentificeerd.
• Aan elke voortbrenger ${\displaystyle s\in S}$ wordt een kleur ${\displaystyle c_{s}}$ toegekend.
• Voor elke ${\displaystyle g\in G}$ en ${\displaystyle s\in S}$ worden de knopen die bij de elementen ${\displaystyle g}$ en ${\displaystyle gs}$ behoren, verbonden door een gerichte kant met de kleur ${\displaystyle c_{s}}$ van de voortbrenger. De verzameling kanten ${\displaystyle E(\Gamma )}$ bestaat dus uit de paren van de vorm ${\displaystyle (g,gs)}$, waarin de voortbrenger ${\displaystyle s}$ de kleur van de kant bepaalt.

In de meetkundige groepentheorie wordt gewoonlijk verondersteld dat de verzameling voortbrengers ${\displaystyle S}$ eindig is, 'symmetrisch' is, wat inhoudt dat ${\displaystyle S=S^{-1}}$, en niet het neutrale element van de groep bevat. In dat geval is de Cayley-graaf, op de kleuren na, een gewone graaf: de kanten zijn niet georiënteerd, en de graaf bevat geen cykels.

• Van de oneindige cyclische groep ${\displaystyle \mathbb {Z} }$ met de standaard voortbrenger 1 en zijn inverse −1 (in additieve notatie) is de bijbehorende Cayley-graaf een oneindige keten.

• Het geval met ${\displaystyle G=\mathbb {Z} /n\mathbb {Z} }$, de eindige cyclische groep van orde ${\displaystyle n}$, is vergelijkbaar met het vorige. Ook nu zijn de standaard voortbrengers 1 en zijn inverse −1 en heeft ${\displaystyle S}$ twee elementen. De Cayley-graaf is dan de cyclische graaf ${\displaystyle C_{n}}$.

• De Cayley-graaf van het directe product van een aantal groepen is het cartesisch product van de respectievelijke Cayley-grafen. De Cayley-graaf van de vrije abelse groep ${\displaystyle \mathbb {Z} ^{2}}$ met de 4 voortbrengers ${\displaystyle (\pm 1,\ \pm 1)}$ is een oneindig rooster in het vlak ${\displaystyle \mathbb {R} ^{2}}$, terwijl de Cayley-graaf voor de directe producten ${\displaystyle \mathbb {Z} /n\mathbb {Z} \times \mathbb {Z} /m\mathbb {Z} }$ is een eindig ${\displaystyle n\times m}$-rooster op de torus.

• De bovenste figuur toont de Cayley-graaf van de dihedrale groep ${\displaystyle D_{4}}$ met twee voortbrengers ${\displaystyle a}$ (draaiing over 90° met de klok mee) en ${\displaystyle b}$ (horizontale spiegeling). Aangezien ${\displaystyle b}$ zijn eigen inverse is, zijn de blauwe kanten, die staan voor het uitvoeren van ${\displaystyle b}$, ongericht getekend. Deze keuze van ${\displaystyle a}$ en ${\displaystyle b}$ komt overeen met de presentatie

${\displaystyle \langle a,b|a^{4}=b^{2}=e,ab=ba^{3}\rangle }$.

Het verband tussen de groep en de keuze van de voortbrengers ziet men terug in de Cayley-graaf als cykels. Zo levert bijvoorbeeld ${\displaystyle a^{4}}$ een gesloten pad in de graaf.

• Van de vrije groep met twee voortbrengers ${\displaystyle a}$ en ${\displaystyle b}$ staat de Cayley-graaf met de verzameling voortbrengers ${\displaystyle S=\{a,b,a^{-1},b^{-1}\}}$ eerder in het artikel, waarbij ${\displaystyle e}$ staat voor hetneutrale element. Op een kant naar rechts gaan komt overeen met rechtsvermenigvuldiging met ${\displaystyle a}$, terwijl omhoog gaan vermenigvuldiging met ${\displaystyle b}$ voorstelt. Omdat de vrije groep geen relaties heeft, zijn er geen cycli in de graaf.