Stabilisateur de noeuds d'un graphe de Cayley

KernelPan · July 2020

Bonjour,

je bloque sur la démonstration d'une proposition de mon livre (Groupes finis et treillis de leurs sous-groupes de Alain Debreil, page 139 pour les plus intéressés). Voici :

"Soit $\mathcal{C}(G,S)$ le graphe de Cayley d'un groupe $G$ pour une partie génératrice $S$. Si $H$ est un groupe qui opère sur $\mathcal{C}(G,S)$, alors :

- tous les noeuds de $\mathcal{C}(G,S)$ ont le même stabilisateur (...)."

Une partie de la démonstration :

"Soit $(x,xs)$ un arc de $\mathcal{C}(G,S)$ et soit $h \in Stab(xs)$. Faisons agir $h$ sur cet arc : $h \cdot (x,xs) = (h \cdot x, xs)$. Mais $(x,xs)$ est le seul arc de $\mathcal{C}(G,S)$ étiqueté $s$ et arrivant sur le noeud $xs$, donc $h \cdot x = x$ et donc $Stab(xs) \subset Stab(x)$. Le même argument en partant de $h \in Stab(x)$ montre l'inclusion réciproque (...)."

En réalité, je n'arrive pas à montrer l'inclusion réciproque. En reprenant le même argument, j'obtiens :

$h \cdot (x, xs) = (x, h \cdot xs)$

mais $h \cdot xs$ peut être égal à $xs'$ avec $s'$ un générateur différent de $s$. J'ai pensé à considérer l'arc $(xs,x)$, mais celui-ci n'est en général pas défini pour un système générateur $S$ simplifié. Tout ce que j'arrive à prouver (et c'est normal par la première partie de la démonstration), c'est $Stab(x) \subset Stab(xs^{-1})$.

Pourriez-vous m'aider à me décoincer ?
Merci.

Maxtimax · July 2020

$h\cdot (x,xs)$ n'est-il pas aussi étiqueté par $s$ ? Je pense qu'ici il faut supposer que l'action de $H$ préserve les étiquettes (c'est utilisé dans la première partie de la démonstration)

KernelPan · July 2020

En effet Max, je crois que tu as raison, merci. Si c'est bien ça, je me suis sévèrement compliqué la vie... Je n'avais même pas vu le caractère unique de l'étiquetage et de sa préservation par l'action de H (qui, comme tu l'as dit, semblent être supposés dans la première partie de la preuve), j'ai encore bien des choses à apprendre sur ces graphes. Je vais attendre encore un peu d'autres réponses.

Bonne soirée.

AD · July 2020

Bonjour KernelPan
Maxtimax t'a répondu, mais regardons ce que veut dire qu'un groupe $H$ agit sur $\mathscr C(G,S)$ le graphe de Cayley de $G$ pour la famille génératrice $S$. En d'autres termes, $H$ agit sur les nœuds et sur les arêtes. $$
\begin{array}{ccll}
H\times \mathscr C (G,S) &\longrightarrow &\mathscr C(G,S)\\
(h,x)&\longmapsto&h\cdot x, &\text{pour les nœuds}\\
\big(h,(x,xs)\big)&\longmapsto&(h\cdot x, h\cdot xs) ,&\text{pour les arêtes}
\end{array}
$$ Ainsi définie, l'action préserve les étiquettes des arêtes.
Dans ta question, $(x,h\cdot xs)$ est une arête partant de $x$ et portant l'étiquette $s$, mais par définition de $\mathscr C(G,S)$, il n'y a qu'une arête partant de $x$ et portant l'étiquette $s$, c'est l'arête $(x,xs)$, d'où $h\cdot xs=xs$, montrant que $h\in\mathrm{Stab}(xs)$.

Alain

KernelPan · July 2020

Bonsoir Alain,

et merci beaucoup pour ces compléments. Excuse moi mais je ne suis pas certain de tout comprendre, je ne vois pas pourquoi l'action de H conserve les étiquettes. Du moins, je crois ne pas avoir compris ce que signifie "conserve les étiquettes". Veux-tu dire que :

$h \cdot xs = (h \cdot x)s$ ? (*)

Dans le sens où, si on dispose d'un arc $(x,xs)$ étiqueté par $s$ et que l'on regarde $h \cdot (x,xs)$, alors la conservation de l'étiquette implique la première égalité (*) ? Si oui, je ne vois pas pourquoi...

De toute manière, en regardant un peu les autres pages, mon interprétation des graphes de Cayley était mauvaise. Je travaillerai dessus demain à tête reposée. Par ailleurs je suis désolé si mon message contient des fautes, j'écris sur mon smartphone et je les corrigerai demain en passant sur ordinateur.

AD · July 2020

Bonsoir KernelPan
Il faut bien voir qu'un graphe de Cayley $\mathscr C(G,S)$ est un graphe avec certaines propriétés supplémentaires.
- les nœuds sont les éléments du groupe $G$,
- de chaque nœud $x$ et pour chaque $s\in S$ part une unique arête vers le nœud $xs\ (\in G)$ : $(x,xs)$, arête que l'on étiquette $s$.
Pour qu'un groupe agisse sur un graphe de Cayley, il faut qu'il agisse sur les nœuds du graphe, ce qui induit une action sur les arêtes du graphe, mais cette action doit respecter les propriétés des arêtes, c'est-à-dire les étiquettes.
Ce qui amène à la définition de l'action de $H$ de mon précédent message : $h\cdot$ noeud est un noeud, $h\cdot$ arête est une arête de même étiquette.
Cela revient, comme tu dis, à ce que pour tout $s\in S,\ h\cdot xs=(h\cdot x)s.$
Si l'action de $H$ ne vérifie pas cela, c'est (peut-être) une action sur un graphe, mais pas sur un graphe de Cayley $\mathscr C(G,S)$.
Alain

KernelPan · July 2020

Bonjour AD,

merci infiniment pour cette réponse. Comme je n'ai jamais fait de théorie des graphes, je partais avec un handicap et j'ai mélangé apparemment plein de choses. Je vois maintenant comment un graphe de Cayley se présente (et je suis totalement en tort, l'une de tes propositions en donnait la description complète avec les nœuds et le nombre de flèches entrantes/sortantes), et je comprends bien mieux ce qui signifie une action de groupe sur ce dernier.

Je vais retravailler tout ça aujourd'hui, en espérant ne pas tout mélanger.

Bonne journée.

Stabilisateur de noeuds d'un graphe de Cayley

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 3