Chapitre 4 Catégories et graphes de Cayley

4.1 Groupes avec générateur,graphes orientés connexes pointés

On peut construire une catégorie GrGe dont les objets sont les groupes munis d'un générateur, les morphismes entre (G,S) et (H,T) étant les morphismes de groupes f:G® H tels que de plus f(S)Ì T. Cette catégorie a un élément initial (le groupe à 1 élément avec le générateur vide), un élément final (le groupe à 1 élément avec le générateur formé de cet élément), des sommes (la somme de (G,S) et (H,T) est la somme dans Grp de G et S avec le générateur union des images de S et T dans ce groupe-somme).

On peut construire une catégorie GrOP dont les objets sont les (G,g) avec G graphe orienté et g sommet spécial de G. Les morphismes sont les morphismes de graphes orientés (option 2): application f des sommets vers les sommets de sorte que f(u)=f(v) ou bien f(u)f(v) arc si uv arc, l'image du sommet spécial est le sommet spécial.

On a un foncteur Cay, qui attribue à un groupe muni d'un générateur (G,S) le graphe Cay(G,S) avec le sommet spécial qui correspond au neutre de G.

Il y a un adjoint à droite (disons Yac) de Cay, qui s'obtient en associant au graphe orienté connexe avec un sommet spécial (G,g), le groupe libre sur l'ensemble des arcs de G, quotienté par les cycles de G.

Si on a un graphe pointé connexe (G, g) et un groupe G avec une partie génératrice S, pour chaque morphisme de graphes pointés G,g vers Cay(G,S), il y a un morphisme de groupes Yac(G,g) vers (G,S) qui envoie l'élément u correspondant à un arc u de G vers l'élément de G qui fournit l'arc image de u dans Cay(G,S). Et ceci réalise une bijection.

4.1.1 Variantes

Une construction similaire peut se faire avec les groupes abéliens au lieu des groupes en général.

On peut aussi utiliser les graphes non-orientés et les groupes munis d'un générateur formé d'éléments involutifs du groupe.

4.1.2 Exemple

G est formé des deux arcs a de but g et b de source g. Alors Y=Yac(G) est le groupe libre sur 2 éléments, muni de son générateur {a,b}. Le graphe de Cayley de (Y,{a,b}) est un arbre où chaque sommet a deux arcs sortants provenant de a et b et deux arcs entrants provenant de a et b. Tout morphisme f (dans GrOP) de (G,g) vers un graphe de Cayley Cay(G,S) donne un arc f(a) arrivant en f(g), c'est-à-dire un arc (x,e) avec x^-1Î SÌ G et un arc f(b) partant de f(g), c'est-à-dire un arc (e,y) avec yÎ SÌ G. Il y a alors un unique morphisme de groupes qui envoie Y sur G, avec a|® x^-1 et b|® y.

4.2 Graphes coloriés

On peut essayer de perdre moins d'information sur la structure en gardant la partition des arcs selon l'élément (du groupe) qui a servi à les construire. On aura donc ainsi a considérer un foncteur CayC (Cayley colorié) qui à un groupe muni d'une partie génératrice associe le graphe pointé orienté connexe muni de cette partition.

Les morphismes entre les graphes coloriés sont bien entendu les morphismes de graphes qui de plus envoient des arcs de la même classe du graphe source sur des arcs de la même classe dans le graphe but.

Il y a alors un adjoint à droite. On forme le groupe libre sur les arcs, comme pour Yac et on quotiente ensuite par les relateurs a=b provenant des paires d'arcs a,b prises dans la même partie de la partition.

4.2.1 Exemple

Le graphe est le triangle colorié T de la figure 4.1.a, le groupe est alors

avec a qui correspond à 1 et b à -2. Un morphisme de graphes coloriés etc. de T vers un graphe de Cayley Cay(G,S) envoie l'arc colorié a issu de g vers un arc (e,x) partant du sommet spécial e de Cay(G,S), l'arc colorié a de but g vers un arc (y,e) de même classe que (e,x), ce qui veut dire y=x^-1 et enfin l'arc colorié b va vers l'arc (x,y), qui provient donc de x^-2.

Ceci correspond bien à un morphisme de groupes qui envoie a sur x et b sur x^-2.

Figure 4.1 : Deux triangles coloriés

Il va de soi que si les parties de la partition sont toutes réduites à un élément, le groupe formé est le même qu'à la section précédente.

Il arrivera, surtout si les parties sont trop grosses, que les morphismes vers les graphes de Cayley ne puissent pas être injectifs.

Par exemple dans le triangle de la figure 4.1.b, les deux sommets de droite ont forcément la même image. Ceci se voit déjà dans le groupe, les relations abc^-1=e (cycle) et a=c (coloration) impliquent b=e.