fr.wikipedia.org

Graphe de Cayley — Wikipédia

️Tue Apr 01 2014

Un article de Wikipédia, l'encyclopédie libre.

En mathématiques, un graphe de Cayley (du nom d'Arthur Cayley) est un graphe qui encode la structure d'un groupe. C'est un outil important pour l'étude de la combinatoire et de la géométrie des groupes. La structure et la symétrie des graphes de Cayley ont font de bons candidats pour construire des graphes expanseurs.

Familles de graphes définies par leurs automorphismes
distance-transitif	→	distance-régulier	←	fortement régulier
↓
symétrique (arc-transitif)	←	t-transitif, (t ≥ 2)		symétrique gauche (en)
↓
_{(si connexe)} sommet-transitif et arête-transitif	→	régulier et arête-transitif	→	arête-transitif
↓		↓		↓
sommet-transitif	→	régulier	→	_{(si biparti)} birégulier
↑
graphe de Cayley	←	zéro-symétrique		asymétrique

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

Certains auteurs n'exigent pas que $S$ engendre le groupe. Dans ce cas, $\Gamma$ n'est pas toujours connexe ; ses composantes connexes correspondent aux classes suivant le sous-groupe engendré par $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 $v_{g}$ à $v_{s*g}$ ).

{\displaystyle D_{4}} — Graphe de Cayley du groupe diédral $D_{4}$ pour les deux générateurs $a$ et $b$ .

Le graphe de Cayley du groupe diédral $D_{4}$ avec deux générateurs $a$ et $b$ , vérifiant les relations $a^{4}=b^{2}=e,ab=ba^{3}$ est représenté sur la gauche. Les flèches rouges représentent la composition par $a$ , et les bleues celles par $b$ . Un graphe de Cayley de $D_{4}$ différent est représenté à droite : $b$ est toujours la réflexion horizontale et est représentée en bleu, mais $c$ est maintenant une symétrie par rapport à une diagonale. Puisque les deux sont d'ordre 2, le graphe n'est pas orienté.
Le graphe de Cayley du groupe libre à deux générateurs est représenté en haut à droite de la page. ( $e$ est l'élément neutre). Un pas vers la droite correspond à une multiplication par $a$ , vers la gauche par $a^{-1}$ , vers le haut par $b$ et $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. Ceci est un élément clé dans la preuve du paradoxe de Banach-Tarski.
Plus généralement, le treillis de Bethe, ou arbre de Cayley est le graphe de Cayley du groupe libre à $n$ générateurs. À une présentation d'un groupe $G$ par $n$ générateurs correspond un morphisme surjectif de groupe de l'arbre de Cayley dans le groupe de Cayley de $G$ . Si l'on interprète topologiquement les graphes comme des CW-complexes de dimension 1, l'arbre de Cayley est le revêtement universel du graphe de Cayley, et le noyau de la projection est le groupe fondamental du graphe de Cayley.

À droite se trouve un dessin du graphe de Cayley d'un groupe d'ordre 18 avec présentation $\langle x,y,z\mid x^{2}=y^{2}=z^{2}=(xy)^{3}=(xz)^{3}=(yz)^{3}=(xyz)^{2}=1\rangle$ . 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).

↑ Daniel Peter Theron, An extension of the concept of graphically regular representations (thèse), University of Wisconsin, Madison, 1988 (MR 2636729), p. 46.

Métrique des mots

(en) Eric W. Weisstein, « Cayley Graph », sur MathWorld

(en) Arthur Cayley, « On the theory of groups », Proc. London Math. Soc., n^o 9,‎ 1878, p. 126-133
(en) H. S. M. Coxeter et W. O. J. Moser (de), Generators and Relations for Discrete Groups, Springer, 1972 (réimpr. 2013), 3^e éd. (1^re éd. 1957), 164 p. (ISBN 978-3-662-21946-1, présentation en ligne), « 3. Graphs, Maps and Cayley Diagrams », p. 18-32.