Défi du week-end

raoul.S

Petit défi sans prétention : 

Soit $n\geq 2$, on considère le graphe $G_n=(V,E)$ dont les sommets sont les éléments de l'ensemble $V:=\{\{a,b\}\mid\, a,b\in [\![1,n]\!],\ a\neq b\}$ avec $a,b\in [\![1,n]\!]$ (les parties à deux éléments de $[\![1,n]\!]$) et les arêtes sont les éléments de l'ensemble $E:=\{\{s_1,s_2\}\mid\, s_1,s_2\in V, \ s_1\cap s_2=\emptyset\}$.

Déterminer le groupe des automorphismes du graphe $G_n$ pour $n\geq 2$.

Rappel : un automorphisme est une bijection $\phi:V\to V$ qui respecte les arêtes, donc telle que $\{\phi(s_1),\phi(s_2)\}\in E$ ssi $\{s_1,s_2\}\in E$

JLT

Je n'ai pas regardé en détail mais il me semble que c'est $S_n$ pour $n\geqslant 3$. On le voit à la main pour $n=3$. Pour $n\geqslant 4$ on considère l'ensemble $V'$ des sous-graphes complets ayant $n-1$ sommets et on montre que $V'$ est en bijection avec $V$.

raoul.S

J'avoue ne pas comprendre ton argument avec $V'$ @JLT, peut-être je dois comprendre ceci : tout automorphisme envoie un sous-graphe complet sur un sous-graphe complet donc tout automorphisme induit une permutation de l'ensemble $V'$ ?

En tout cas j'ajoute ci-dessous les graphes obtenus pour $n=4$ et $n=5$ au cas où : 

n=4



n=5

LOU16

Bonjour,

Je me suis contenté du cas $n=4$, où je parviens  à une conclusion qui diffère de celle de JLT.

$G_4=(V,E), \:\:\#V=6,\quad V=\{a,b,c,d,e,f\},\quad E=\Big\{ \{a,b\} ,\{c,d\} ,\{d,e\}\Big\}.\quad \mathcal G:=\text{Aut }G_4$

$\mathcal G$ agit transitivement sur $V, \quad|\mathcal G|=6|\mathcal S(a)|\quad$ où $\:\mathcal S(a)=\{\sigma \in\mathcal G\mid \sigma(a)=a\}.\:\forall \sigma \in \mathcal S(a), \:\sigma (b)=b.$

La restriction de $\: \sigma$ à $ G'=(V',E')\:\Big(V'=\{c,d,e,f\},\:E'=\Big\{\{c,d\},\{e,f\}\Big\}\Big)$ est un automorphisme de  $G'.\quad |\mathcal S(a)| =8.$

$$|\mathcal G| =48\:\text { et d'autre part }, \mathcal G \text { contient un sous-groupe isomorphe à } \mathfrak S_4.$$

AD

Bonjour Lou16

Cela me rappelle l'article de la RMS (année 131 N°2, Janvier 2021, p 9-13) "Le seul groupe d'ordre 48 contenant $\mathfrak S_4$ est $\mathfrak S_4\times C_2$" (le groupe total du cube).

Alain

JLT

Bon j'aurais dû réfléchir avant d'écrire.

raoul.S

@JLT disons que $n=4$ est l'intrus...

@LOU16 c'est lequel le sous-groupe de $\text{Aut }G_4$ isomorphe à $\mathfrak S_4$ ?

LOU16

@raoul.S

$X=\{1,2,3,4\}, \:V=\mathcal P_2(X).$

Soit $\pi$ le morphisme injectif: $\:\mathfrak S_X\to\mathfrak S_V\: $ défini par $\forall \sigma \in\mathfrak S_X,\:\:\pi(\sigma): \{x,y\}\mapsto \{\sigma(x) , \sigma (y) \}.\quad $ Alors:

 $$\:\pi(\mathfrak S_X) \text{ est un sous-groupe de }\: \mathcal G,\:\text{ isomorphe à }\mathfrak S_4.$$

JLT

Déjà j'avais mal lu la définition, j'avais considéré le graphe $G'_n$ tel que $s_1$ et $s_2$ est une arête si $s_1\cap s_2\ne\emptyset$, mais ça ne change rien au problème. Mon raisonnement était le suivant : pour tout $a\in [\![1,n]\!]$, on considère le sous-graphe $\Gamma_a$ dont les sommets sont les parties de la forme $\{a,x\}$ ($x\in [\![1,n]\!]$). Si je ne me trompe pas cette fois, pour $n\geqslant 5$, l'application $a\mapsto \Gamma_a$ est une bijection entre $[\![1,n]\!]$ et l'ensemble des sous-graphes complets de $G'_n$ ayant $n-1$ sommets. Tout automorphisme de $G_n$ induit donc une permutation de $[\![1,n]\!]$.

raoul.S

Oui effectivement. Pour résumer, l'injection de LOU16 $\mathfrak S_n\hookrightarrow \text{Aut}(G_n)$ qui est valable pour tout $n\geq 3$ et l'injection de JLT $\text{Aut}(G_n)\hookrightarrow \mathfrak S_n$ valable pour tout $n\geq 5$ montrent que $\text{Aut}(G_n)\simeq \mathfrak S_n$ pour tout $n\geq 5$.

Les cas $n=1,2,3$ sont évident. Il reste le cas $n=4$. Pour ce cas j'avais trouvé un produit semi-direct $\text{Aut }G_4\simeq C_2^3\rtimes \mathfrak S_3$ mais la solution de Lou16 et la remarque de AD montrent que l'on a plus simplement : $\text{Aut}(G_4)\simeq C_2\times \mathfrak S_4$.

@AD est-ce que tu as une preuve ou tu peux me dire où je peux en trouver une de ton affirmation ICI ? Je ne peux pas me connecter à la RMS...

PS. ah oui, une dernière chose, les graphes ci-dessus sont connus sous le nom de Graphes de Kneser.

Math Coss

Si on a un groupe $G$ d'ordre $48$ qui contient un sous-groupe $K$ isomorphe à $\mathfrak{S}_4$ (je considérerai que c'est une égalité désormais), alors $K$ est d'indice $2$ donc distingué. Cela me repose les yeux d'écrire une suite exacte : \[1\to\mathfrak{S}_4\longrightarrow G\stackrel{\pi}{\longrightarrow} \Z/2\Z\to1.\] On choisit un antécédent $\tau$ de l'élément non trivial de $\Z/2\Z$ par $\pi$. La conjugaison par $\tau$ dans $G$ induit un automorphisme de $\mathfrak{S}_4$. On sait que tout automorphisme de $\mathfrak{S}_4$ est intérieur (c'est vrai pour $\mathfrak{S}_n$ si $n\ne6$). Il existe donc $\sigma\in\mathfrak{S}_4$ tel que pour tout $k\in\mathfrak{S}_4$, on ait $\tau k\tau^{-1}=\sigma k\sigma^{-1}$, d'où $(\sigma^{-1}\tau)k(\sigma^{-1}\tau)^{-1}=k$. Vu que $\pi(\sigma^{-1}\tau)=\pi(\tau)$, on peut remplacer $\tau$ par $\sigma^{-1}\tau$ et, ainsi, supposer que $\tau$ commute avec $K=\mathfrak{S}_4$.

Par ailleurs, $\tau^2\in\ker\pi=\mathfrak{S}_4$ et, de même que $\tau$, il commute à $\mathfrak{S}_4$. Comme le centre de $\mathfrak{S}_4$ est trivial, on obtient que $\tau$ est d'ordre $2$ et, en définitive, que $G$ est le produit direct annoncé : $\mathfrak{S}_4\times\Z/2\Z$.

gebrane

Dommage,  le défi touche un public restreint. 

raoul.S

@Math Coss super, merci

@gebrane le défi était plutôt élémentaire pour $n\neq 4$.

raoul.S

D'ailleurs je viens de me rendre compte que l'on peut traiter le cas $n=4$ sans utiliser le résultat de AD. Honte à moi...

En reprenant les notations de LOU16, $G_4=(V,E), \:\:\#V=6,\quad V=\{a,b,c,d,e,f\},\quad E=\Big\{ \{a,b\} ,\{c,d\} ,\{d,e\}\Big\},$ on considère la permutation $\sigma:=(a\, b)(c\, d)(e\, f)$. C'est un automorphisme de $G_4$. On a évidemment pour tout $\phi\in \text{Aut} G_4$, $\phi\sigma\phi^{-1}=(\phi(a)\, \phi(b))(\phi(c)\, \phi(d))(\phi(e)\, \phi(f))=\sigma$. Donc $<\sigma>$ est normal dans $\text{Aut} G_4$. Vu que $\sigma$ n'appartient pas au sous-groupe $\mathfrak{S}_4$ définit par LOU16 ICI, et que ce dernier est lui aussi normal (car d'indice 2) on a $\text{Aut} G_4\simeq \mathfrak{S}_4\,\times <\sigma>$.

Thierry Poma

@raoul.S : bonjour. J'espère que tu vas bien. J'ai du mal à comprendre ceci :

(...) les éléments de l'ensemble $V:=\{\{a,b\}\mid\, a,b\in [\![1,n]\!],\ a\neq b\}$ avec $a,b\in [\![1,n]\!]$ (les parties à deux éléments de $[\![1,n]\!]$)

raoul.S

Salut @Thierry Poma, $V$ est simplement l'ensemble des parties à deux éléments de $[\![1,n]\!]$. On note ça également $\mathcal P_2([\![1,n]\!])$ je crois.

Par exemple si $n=3$ alors $V=\{\{1,2\},\{1,3\},\{2,3\}\}$.

Thierry Poma

@raoul.S : je voulais attirer ton attention sur le texte. Ne devrait-on pas le lire ainsi ?

(...) les éléments de l'ensemble $V:=\{\{a,b\}\mid\, a,b\in [\![1,n]\!],\ a\neq b\}$ (i.e. $V$ est l'ensemble des parties à deux éléments de $[\![1,n]\!]$)

Dit autrement, je ne vois pas ce que vient faire ceci : (...)  avec $a,b\in [\![1,n]\!]$ (...)

raoul.S

Oui tu as raison, j'avais d'abord écrit d'une façon puis d'une autre, par conséquent j'ai obtenu un mix des deux et j'ai oublié de supprimer ce morceau...  

raoul.S

En fait le cas $n=4$ m'a fait regarder de plus près les graphes constitués d'un nombre fini d'arêtes disjointes comme ci-dessous : 



cette fois on note $n$ le nombre d'arêtes, les sommets d'en "haut" étant notés $a_i$ et ceux du "bas" $b_i$. J'ai cherché à exprimer le plus simplement possible le groupe des automorphismes d'un tel graphe. J'obtiens ça : 

$$\text{Aut} G_n\simeq \left(\Z/2\Z\right)^n\rtimes_f \mathfrak{S}_n$$

où $f:\mathfrak{S}_n\to \text{GL}_n\left(\Z/2\Z\right)$ est le morphisme défini par $\sigma\in \mathfrak{S}_n\mapsto M_{\sigma}$ avec $M_{\sigma}$ la matrice de permutation associée à $\sigma$.

Pour $n=2$ on peut exprimer plus simplement ce groupe, car on a : $\left(\Z/2\Z\right)^2\rtimes_f \mathfrak{S}_2\simeq D_8$, où $D_8$ est le groupe diédral du carré.

Pour $n=3$ grâce au remarques de LOU16 et AD on a : $\left(\Z/2\Z\right)^3\rtimes_f \mathfrak{S}_3\simeq \mathfrak{S}_4\times C_2$.

Par contre je ne sais pas si pour $n>3$ on peut exprimer plus simplement ce groupe. Si quelqu'un a une idée ça m'intéresse.

Math Coss

Ce sont des groupes de Coxeter de type B (ou C).

raoul.S

Ok merci Math Coss.

Math Coss

Plutôt que le groupe affine sur $\Z/2\Z$, il est habituel de représenter ce groupe comme celui des matrices monomiales dont les coefficients (un seul non nul par ligne et par colonne, par définition) valent $\pm1$. Cela rend le groupe prêt à agir sur les systèmes de racines, dans $\R^n$ euclidien standard dont on note $(e_i)$ la base canonique : \[\Delta_B=\{e_i-e_j\mid 1\le i\ne j\le n\}\cup\{e_i\mid 1\le i\le n\}\quad\text{et}\quad \Delta_C=\{e_i-e_j\mid 1\le i\ne j\le n\}\cup\{2e_i\mid 1\le i\le n\}.\]Ces groupes sont engendrés par les réflexions qu'ils contiennent, qui sont exactement les réflexions par rapport aux hyperplans orthogonaux aux éléments de $\Delta$.

raoul.S

Ok, finalement tout ça va plus loin que ce que je pensais. J'ai regardé en diagonal quelques documents et il y a toute une théorie sur ces groupes de Coxeter. Ceux du présent fil sont de type B on dirait. Mais je vais m’arrêter ici.

gebrane

raoul.S a dit :

 je vais m’arrêter ici.

Non raoul. Si je remplace ton V par $V:=\{\{a,b\}\mid\, a,b\in [\![1,n]\!],\, pgcd(a,b)=1\}$, ça change peu ou tout ?

raoul.S

Tu supprimes des sommets, on obtiendra des groupes totalement différents probablement. Mais là je dois aller chasser sur ma PS4, gebrane . Mais mets-toi à l'aise et continue ton raisonnement, je lirais plus tard...

gebrane

Pour n=2ou 3 c'est pareil. Pour n=4, un sommet explose. Cela me donne l'idée de jouer à rust aussi . Bonne fin de semaine

AD

raoul.S a dit : https://les-mathematiques.net/vanilla/index.php?p=/discussion/comment/2417890/#Comment_2417890

AD est-ce que tu as une preuve ou tu peux me dire où je peux en trouver une de ton affirmation ICI ? Je ne peux pas me connecter à la RMS...

Avec un peu de retard, voici l'article de la RMS en question.

Il présente une preuve dans un tout autre style que celle en dix lignes de MathCoss ci-dessus.
Toutefois je pense qu'elle pourrait intéresser certains ?

Alain

raoul.S

Merci beaucoup @AD, c'est sympa