Graphe de Cayley

Étant donné un groupe ${\displaystyle (G,*)}$ et une partie génératrice ${\displaystyle S}$ de ce groupe, le graphe de Cayley Cay(G,S) est construit comme suit :

• À chaque élément ${\displaystyle g}$ de ${\displaystyle G}$, on associe un sommet ${\displaystyle v_{g}}$.
• À chaque élément ${\displaystyle s}$ de ${\displaystyle S}$, on associe une couleur ${\displaystyle c_{s}}$.
• Pour tout ${\displaystyle g\in G}$ et ${\displaystyle s\in S}$, on trace une arête orientée de couleur ${\displaystyle c_{s}}$ du sommet ${\displaystyle v_{g}}$ vers le sommet ${\displaystyle v_{g*s}}$.

On peut aussi associer à chaque générateur une direction plutôt qu'une couleur, mais il est alors parfois impossible de représenter le graphe dans le plan. Dans certains contextes, on utilise la multiplication à gauche plutôt qu'à droite (les arêtes vont alors de ${\displaystyle v_{g}}$ à ${\displaystyle v_{s*g}}$).

• Comme l'ensemble générateur d'un groupe n'est pas unique, la structure des graphes de Cayley d'un groupe donné n'est pas unique.
• Si l'ensemble générateur a ${\displaystyle n}$ éléments, chaque sommet a ${\displaystyle n}$ arêtes entrantes, et ${\displaystyle n}$ arêtes sortantes.
• Les cycles du graphe correspondent aux relations vérifiées par les générateurs.
• Si ${\displaystyle s}$ et ${\displaystyle s^{-1}}$ sont tous les deux dans l'ensemble de générateurs, on remplace souvent chaque paire d'arêtes orientées correspondant à ${\displaystyle s}$ et ${\displaystyle s^{-1}}$ par une seule arête non orientée.

Le graphe de Cayley du groupe libre à deux générateurs est représenté en haut à droite de la page. (${\displaystyle e}$ est l'élément neutre). Un pas vers la droite correspond à une multiplication par ${\displaystyle a}$, vers la gauche par ${\displaystyle a^{-1}}$, vers le haut par ${\displaystyle b}$ et ${\displaystyle b^{-1}}$ vers le bas. Comme il n'y a pas de relations dans le groupe libre (par définition), son graphe de Cayley est acyclique.

À droite se trouve un dessin du graphe de Cayley d'un groupe d'ordre 18 avec présentation ${\displaystyle <x,y,z|x^{2}=y^{2}=z^{2}=(xy)^{3}=(xz)^{3}=(yz)^{3}=(xyz)^{2}=1>}$. Il est engendré par trois éléments d'ordre 2, qui sont donc représentés par des arêtes non-orientées de trois couleurs différentes; chaque sommet est lié à une arête de chaque couleur. En suivant les arêtes on peut vérifier que les autres relations sont satisfaites. Si par exemple pour les générateurs x, y, et z on choisit respectivement les couleurs rouge, vert, et bleu (mais peu importe, la présentation est parfaitement symétrique), on voit que, partant d'un sommet quelconque, la suite rouge-vert-rouge-vert-rouge-vert nous remet à notre point de départ (alors (xy)³ = 1), et aussi la suite rouge-vert-bleu-rouge-vert-bleu (alors (xyz)² = 1).