Evaristette, septembre 2018
Chères amies, chers amis de Galois, voici l'evaristette de septembre:
Galois est considéré comme l'initiateur de la théorie des groupes. En
tout cas, le groupe des permutations des racines d'une équation est au
cœur de sa théorie. Soit G le groupe de toutes les permutations des
entiers de 1 à n. On sait qu'il peut être engendré par n-1
transpositions, .... c'est dans tous les livres mais sauriez-vous
montrer qu'il ne peut être engendré par n-2 transpositions. Supplément :
trouver une condition nécessaire et suffisante pour qu'un ensemble de
n-1 transpositions engendre G.
A vos plumes (d'oie)! Ce 26 septembre, un "ami de Galois" [https://www.evaristegalois.org/]
Galois est considéré comme l'initiateur de la théorie des groupes. En
tout cas, le groupe des permutations des racines d'une équation est au
cœur de sa théorie. Soit G le groupe de toutes les permutations des
entiers de 1 à n. On sait qu'il peut être engendré par n-1
transpositions, .... c'est dans tous les livres mais sauriez-vous
montrer qu'il ne peut être engendré par n-2 transpositions. Supplément :
trouver une condition nécessaire et suffisante pour qu'un ensemble de
n-1 transpositions engendre G.
A vos plumes (d'oie)! Ce 26 septembre, un "ami de Galois" [https://www.evaristegalois.org/]
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
on peut procéder en prouvant que dans $S_n$, il existe toujours un élément qui ne peut être écrit comme produit de $n-2$ transpositions: ce sont les $n-$cycles, c'est-à-dire les cycles dont le support est de cardinal $n$.
On peut le démontrer par l'absurde.
Cordialement
...
En composant cette permutation avec n'importe quelle transposition $(i,j)$, on constate que ce cardinal augmente ou diminue de $1$ selon que $i$ et $j$ sont dans le même cycle ou dans des cycles différents.
Si on compose $\sigma$ avec $k$ transposition,$C_{\sigma}$ augmente ou diminue d'au plus $k$.
Sachant que le cardinal de la permutation "Identité" est $n$ et que celui d'un cycle d'ordre $n$ est $1$, on voit que le nombre de transpositions nécessaires pour transformer un $n$-cycle en $n$ cycles d'ordre $1$ ne peut-être inférieur à $n-1$.
...
Il me semble que l'affirmation initiale est exacte. Par contre la démonstration ne me suffit pas : le groupe engendré par $n-2$ transpositions peut contenir des éléments qui sont composés de plus de ces $n-2$ transpositions, il suffit de faire des répétitions...
On considère un enemble fini $E$ et un ensemble $\mathcal T$ de transpositions de $E$. On représente les éléments de $E$ par des points, et l'on joint deux de ces points si la transposition qui les échange est élément de $\mathcal T$. On obtient ainsi un graphe non orienté. L'ensemble $\mathcal T$ engendre le groupe de toutes les permutations de $E$ si et seulement si l'on peut se rendre de n'importe quel point à n'importe quel autre en suivant les arêtes du graphe, autrement dit si le graphe est connexe. Il n'est pas difficile de démontrer qu'un graphe connexe à $n$ sommets a au moins $n-1$ arêtes.
Si le graphe n'est pas connexe, ses composantes connexes donnent le groupe de permutations engendré par $\mathcal T$.
Qu'on ne se méprenne pas : j'avais vu ça il y a longtemps et je ne connais presque plus rien à la théorie des graphes : encore une chose que je regrette... mais cette vision imagée extraite de ma mémoire me semble très parlante.
Bonne soirée.
Fr. Ch.
M
Un graphe à $n$ sommets et $n-1$ arêtes n'est pas forcément un arbre.
Il y a les transpositions $(1,i)$, $2 \le i \le n$, ce qui correspond effectivement à un arbre.
Il y a aussi les transpositions $(i,i+1)$, $1 \le i \le n-1$, ce qui correspond à une « chaîne » pour ainsi dire, je ne sais si ça a un nom en théorie des graphes.
Mais il y a une foule d'autres ensembles de $n-1$ transpositions qui engendrent le groupe symétrique.
Bonne soirée.
Fr. Ch.
Bonne journée.
Fr. Ch.
C'est aussi le nombre de façons d'exprimer un $n$-cycle comme un produit de $n-1$ transpositions (suite A000272 de l'OEIS).