Skip to content

Groupe d'automorphisme des graphes

Nous apprécions votre aide pour développer nos tutoriels sur l'informatique.

Solution :

Voici une réponse complète.

  • La réponse à Q1 est 'non, car $A_w={1,2}$ et $A_s={1}$'.

  • La réponse à Q2 est 'non, car $A_w$ contient simplement.'. deux alors que $A_s$ contient seulement un élément.

  • La réponse à la question 3 est " le plus petit élément de $A_w$ et de $A_s$ est 1 ".

Cela découlera des propositions 1 et 2 ci-dessous.

Digression en vue d'une recherche future.

La question est facile principalement parce que le PO a utilisé des quantificateurs universels dans les définitions des ensembles., au lieu de

en demandant de caractériser quelles permutations " forcent " qui.

Alors qu'une réponse complète à la question du PO sera donnée plus loin, une réponse plus interprétation plus ambitieuse de la question du PO en est une autre, pas tout à fait littérale : pour la formuler, il faut d'abord définir, pour tout $(pi_0,pi_1)inmathfrak{S}_ntimesmathfrak{S}_n$,

pi_0$ force $pi_1$

à signifier :

pour chaque graphe $G$ sur $n$, si $pi_0$ est un automorphisme de $G$, alors $pi_1$ est un automorphisme de $G$ aussi.

(Évidemment, " forces " est une relation binaire réflexive et transitive ; elle n'est pas symétrique dès que $ngeq 3$. Elle n'est pas non plus en général antisymétrique : par exemple, si pour tout $t$ copremier à $n$, le cycle $pi:=(0,1,dotsc,n-1)$ force $pi^t$, mais $pi^tneqpi$ force aussi $pi$. Donc 'forces' en général n'est ni une relation d'équivalence ni un ordre partiel).

L'évidence interprétation ambitieuse est :

Étant donné $ninomega$, caractériser la relation 'forces', c'est-à-dire caractériser l'ensemble $F(n) = { (pi_0,pi_1)inmathfrak{S}_ntimesmathfrak{S}_ncolon pi_0 mathrm{forces} pi_1}$.

De plus :

Analyser le problème de décision d'appartenance à $F(n)$.

Ceci semble être une question de recherche difficile. Par exemple, il est très douteux qu'en général il existe un certificat de taille polynomiale pour l'appartenance à $F(n)$.

Réponse à la question.

Soit $n={0,1,dotsc,n-1}$, et si $Esubseteq.[n]^2:={ emid esubseteq n, lvert ervert=2}$, alors on écrit $mathrm{Aut}(n,E)$ pour le groupe d'automorphisme du graphe $(n,E)$.

Pour tout $ninomega$ laissons

$S(n) := { (pi_0,pi_1)inmathfrak{S}_ntimesmathfrak{S}_ncolonquad pi_1notinlanglepi_0rangle }subsetneqmathfrak{S}_ntimesmathfrak{S}_n$.

Définissez la formule

$xi(pi_0,pi_1)$ $qquad:=qquad$ $existe Esubseteq[n]^2quadpi_0inmathrm{Aut}(n,E)$ $wedge$ $pi_1notinmathrm{Aut}(n,E)$.

(Les seules variables libres sont $pi_0$ et $pi_1$).

Votre question porte sur l'ensemble

$A_w$ $:=$ $biggl{\N{i1}Nous sommes tous (pi_0,pi_1) dans S(n) qquad xi(pi_0,pi_1) biggr}$.

$A_w={1,2}$.

Preuve de la proposition 1. Pour $nin{1,2}$, toute permutation de $n$ est cyclique, donc $S(n)=emptyset$, d'où le quantificateur universel dans $A_w$ vacillement satisfait. Par conséquent, ${1,2}subseteq A_w$.

Pour prouver ${1,2}supseteq A_w$, nous prouvons l'affirmation équivalente ${ ainomegamid ageq 3}cap A_w = emptyset$.

Soit un $ngeq 3$ quelconque. Soit $cdot text{m} n$ une abréviation de $cdot text{mod} n$, c'est-à-dire la fonction

$mathbb{Z}long-flèche droite n$

$alongmapsto$ unique plus petit élément non négatif de l'ensemble ${ a+ nzmid zinmathbb{Z}}$.

Soit $pi_0colon nto n$ défini par

$pi_0(i)=(i+1)mathrm{m} n$.

(Inutile de préciser que la notation usuelle est $pi_0=(0,1,dotsc,n-1)$. Nous aurons l'utilité de la formulation ci-dessus plus tard).

Définir

$pi_1colon nlongrightarrow n$

$ilongmapsto (n-i) text{m} n$.

Alors $pi_1$ n'est pas une puissance de $pi_0$ (car s'il existait $einomega$ avec $pi_1=pi_0^e$, alors en particulier $pi_1(0)=pi_0(0)^e$ et $pi_1(1)=pi_0(1)^e$, c'est-à-dire. $(n-0)\N{mathrm{m}N = ecdot(0+1)N{mathrm{m}N$ et $(n-1)N{mathrm{m}N = ecdot(1+1)N{mathrm{m}N$, c'est-à-dire. $0=e mathrm{m} n$ et $(n-1)mathrm{m} n=2e mathrm{m} n$, ce qui implique la contradiction $0=(n-1)mathrm{m} n$).

D'où $(pi_0,pi_1)dans S(n)$ ; ainsi, si l'on prouve que $xi(pi_0,pi_1)$ est faux, alors $nnot dans A_w$ et la preuve est complète.

Or, $xi(pi_0,pi_1)$ étant faux est équivalent à .

$Pour tout Esous-ensembleq[n]^2quadpi_0notinmathrm{Aut}(n,E)$ $vee$ $pi_1inmathrm{Aut}(n,E)$ $hspace{50pt}$ (N).

Nous prouvons maintenant (N) ; laissons tout $Esous-ensembleq[n]^2$ soit donné. Si $pi_0notinmathrm{Aut}(n,E)$, il n'y a rien à démontrer ; nous pouvons donc supposer que

$pi_0inmathrm{Aut}(n,E)$ $hspace{170pt}$ (cir)

Nous montrons maintenant que (cir) implique $pi_1inmathrm{Aut}(n,E)$ ; à cette fin, que soit donné tout ${i,j}in E$.

Nous allons montrer

${pi_1(i),pi_1(j)} dans E$ $hspace{160pt}$. (h).

Peu importe que $n$ soit pair ou impair,

$s:=s(i,j):= i+j - frac{n - ( n mathrm{m} 2)}{2}$

est un nombre entier, et

E$ $ni$ ${pi_0^{frac{n + ( n mathrm{m} 2)}{2}-s}(i),pi_0^{frac{n + ( n mathrm{m} 2)}{2}-s}(j)}hspace{50pt}$ (à cause de (cir) et ${i,j} dans E$, et puisque les puissances d'automorphismes sont des automorphismes)

$=$ ${i} (i + frac{i}n + ( n mathrm{m}\ 2)}{2}-s)mathrm{m}} N,N (j + frac{n + ( n mathrm{m}N 2)}{2}-s)Nmathrm{m}} n \}N{40pt}$ (par définition de $pi_0$)

$=$ ${ i + frac{n + ( n mathrm{m} 2)}{2}-(i+j-frac{n - ( n mathrm{m} 2)}{2})mathrm{m}} n , j + frac{n + ( n mathrm{m} 2)}{2}-(i+j-frac{n - ( n mathrm{m} 2)}{2}) mathrm{m} n\N- NN- hspace{25pt}$ (par définition de $s$)

$=$ ${i1} N{i1}- (n-j)NNNNNNNNNN-) n\ ,N- (n-i)NNNNN -mathrm{m}} n }$

$=$ ${ \N- N- N- N- N- N- N- N- N- N- N- N- N- N- N- N- N- N- N- (par définition de $N-N- 1$))

$=$ ${ \N- N- N- N- N- N- N- N- N- N- N- N- N- N- N- N- N- N- espace{50pt}$ (axiome d'extensionnalité)

prouvant (h). Nous avons terminé la preuve que $xi(pi_0,pi_1)$ est faux, c'est-à-dire que $nnotin A_w$. Puisque $ngeq 3$ était arbitraire, la preuve de la proposition 1 est complète.

<>Textebf{i1}Proposition 2.}$ A_s={1}$.

Preuve de la proposition 2. Il est évident que $1dans A_2$. De plus, $2notin A_s$, car il n'existe pas de graphe sur deux sommets avec un groupe d'automorphisme trivial, mais la définition de $A_s$ en partiaire exige qu'il existe un graphe $(n,E)$ avec $mathrm{Aut}(n,E)=langlemathrm{id}rangle$. De plus, si $ngeq 3$, alors exactement le même argument que celui donné dans la preuve de la Proposition 1 ci-dessus prouve que la condition définitoire de l'ensemble $A_s$ est fausse au moins pour la permutation $pi:=(0,1,dotsc,n-1)$, ce qui à cause du quantificateur universel implique déjà $nnotin A_s$. Ceci complète la preuve de la proposition 2.

Remarque 1. Évidemment, l'argument ci-dessus ne fonctionnerait pas pour les graphes dirigés, essentiellement parce que $( pi_1(j) ,pi_1(i) )$ $neq$ $(pi_1(i) ,pi_1(j) )$.

Remarque 2. La condition (cir) est équivalente à ce que $(n,E)$ soit un graphe circulant. L'argument de la preuve de la proposition 1 est l'argument le plus simple que je puisse imaginer pour que.circulants n'ont jamais de groupe d'automorphisme cyclique.

Remarque 3. Comme prédit dans une version antérieure de cette réponse, les graphes circulants sont suffisants pour répondre à la question de l'OP, mais.pour l'interprétation plus ambitieuse, considérer les graphes circulants n'est pas suffisant.

Remarque 4. (ajouté le 26 mars 2018) J'ai travaillé les ensembles $F_{mathrm{ct}}(1)$, $F_{mathrm{ct}}(2)$, $F_{mathrm{ct}}(3)$, $F_{mathrm{ct}}(4)$, $F_{mathrm{ct}}(5)$ en entier. Pour décrire les résultats, il est utile de réduire à types de cycles. On prépare par :

Remarque 5. (ajouté le 6 avril 2018) J'ai travaillé l'ensemble $F_{mathrm{ct}}(6)$ en entier.

Données pertinentes pour le problème de recherche de la compréhension de $F_{mathrm{ct}}(n)$.

On peut trouver un pdf contenant un sur-ensemble des données données données dans ce fil de discussion. ici. (Le service d'hébergement permet de télécharger le---pour 2,6 Mo plutôt grand--- fichier pdf via l'icône sur le côté gauche). Le pdf contient notamment un tableau des 78 types d'isomorphisme de paires de graphes complémentaires non étiquetés sur six sommets, ainsi que tous les types de cycles de permutations de $n=6$.
S'il vous plaît utilisez ces données avec scepticisme; bien que j'ai vérifié les tableaux une fois, j'allais plutôt vite et il n'est pas improbable qu'une erreur subsiste. En particulier, le plus grand tableau a nécessité de travailler à travers 858 décisions de savoir si un type de cycle se produit ou non, donc même si ma probablité d'obtenir une cellule du tableau parfaitement correcte est, disons, 99%,l'espérance du nombre d'erreurs est encore 8,58. J'apprécierais d'être informé des erreurs et je les corrigerai.

Permettez-moi également de mentionner que jusqu'à présent, je n'ai pas eu le temps de vérifier les données avec un ordinateur ; la raison la plus sérieuse pour laquelle je ne l'ai pas fait est que.

il semble qu'il ne soit pas trivial de calculer les classes de conjugaison d'un groupe de permutation arbitraire donné. Il s'agit d'un problème reconnu en algèbre informatique, mais d'après ce que j'ai compris de la littérature spécialisée, les bons algorithmes ne sont connus que sous des hypothèses supplémentaires concernant le groupe de permutation. De façon remarquable, pour les groupes de permutation génériques, la littérature n'a rien de mieux à offrir qu'une sorte d'algorithme de Las Vegas (choisir des éléments du groupe de permutation au hasard jusqu'à ce qu'un ensemble générateur soit trouvé). Je n'ai pas encore essayé de programmer cela ; le tableau a été construit manuellement.

$textbf{Lemma 1.}$ Pour tout $ninomega$, tout graphe $G=(n,E)$ sur $n$, et toute permutation $sigmainmathfrak{S}_n$, pour tout automorphisme $pi$ de $G$,
la permutation $sigma pi sigma^{-1}$ est un automorphisme du graphe $sigma G:=(n,sigma E)$, où $sigma E:={{{sigma(i),sigma(j)}colon {i,j}in E}$.

Preuve. Nous devons montrer que ${i,j}in sigma E$ si $ { ( sigma pi sigma^{-1} )(i) , ( sigmapi sigma^{-1} )(j) } in sigma E$.

Supposons d'abord

(1) ${i,j} Ndans sigma $.

Alors il existe ${i',j'}in E$ avec $i = sigma(i')$ et $j = sigma(j')$. Donc, ${ ( sigma pi sigma^{-1} )(i) , ( sigma pi sigma^{-1} )(j) }$ $=$ ${ ( sigma pi sigma^{-1} )(sigma(i')) , ( sigma pi sigma^{-1} )(sigma(j')) }$ $=$ ${ sigma (pi(i')) , sigma (pi(j'))}$. Puisque (1) ainsi que $pi$ étant un homomorphisme impliquent ${pi(i'),pi(j')} dans E$, il s'ensuit maintenant que ${ sigma (pi(i')) , sigma (pi(j')) } $ est un bord de $sigma E$, comme requis.

Inversement, considérons un quelconque $i,jdans n$ avec

(2) $ { ( sigma pi sigma^{-1} )(i) , ( sigmapi sigma^{-1} )(j) } in sigma E$.

Nous devons montrer que ${i,j}$ $in$ $sigma E$. Par définition de $sigma E$, il s'ensuit que $ { ( pi sigma^{-1} )(i) , ( pi sigma^{-1} )(j) }$ $in$ $E$. Puisque $pi$ est un automorphisme de $(n,E)$, il s'ensuit que ${ sigma^{-1}(i) , sigma^{-1}(j) }$ $in$ $E$ ; par définition de $sigma E$ il s'ensuit que ${ i , j}$ $=$ ${ sigma(sigma^{-1}(i)) , sigma(sigma^{-1}(j)) }$ $in$ $sigma E$, comme requis.
Ceci complète la preuve du lemme 1.

Maintenant, reprenons la définition de $F(n)$ de la digression du début, ainsi que sa version de type cycle :

$textbf{Definition}$($F(n)$, $F_{text{ct}}(n)$)$textbf{.}$ Pour tout $ninomega$ laissons

$F(n):={(pi_0,pi_1)inmathfrak{S}_ntimesmathfrak{S}_nmid pour tout Esous-entendu [n]^2quad pi_0notintext{Aut}(n,E) vee pi_1intext{Aut}(n,E) }$,

Soit $P(n)$ l'ensemble des partitions entières de $n$, pour chaque $lambda dans P(n)$ Soit $Pi(lambda)$ l'ensemble de tous les $piinmathfrak{S}_n$ avec $text{cycletype}(pi)=lambda$, et soit

$F_{text{ct}}(n):={(lambda_0,lambda_1)in P(n)times P(n) mid forall Esubseteq [n]^2forall(pi_0,pi_1)inPi(lambda_0)timesPi(lambda_1)quad pi_0notintext{Aut}(n,E) vee pi_1intext{Aut}(n,E) }$.

Il découle de Lemma 1 que

$F(n) = bigcuplimits_{(lambda_0,lambda_1)in F_{text{ct}}(n)}Pi(lambda_0)timesPi(lambda_1)$.

En ce sens, toute information sur la relation " forces ", c'est-à-dire sur l'ensemble $F(n)$, est contenue dans la relation $F_{text{ct}}(n)$.

L'ensemble $F_{text{ct}}(n)$ est évidemment réflexif et transitif, et non symétrique pour tout $ngeq 3$. Pendant que nous y sommes, permettez-moi de mentionner que je ne vois actuellement pas de réponse à ce qui suit :

Question. Est-ce que $F_{text{ct}}(n)$ est un poset pour tous les $n$ sauf $n=2$ ? C'est-à-dire, est-ce que antisymétrique sauf pour $n=2$ ?

Les figures 1 à 5 suivantes donnent les relations binaires $F_{text{ct}}(n)$ pour $nin{1,2,3,4,5}$. En particulier, les éléments diagonaux sont représentés par des boucles.

Les figures 6 et 7 sont auto-explicatives preuves des figures 1--5. (Vous aurez probablement à zoomer.) J'ignore les permutations d'identité.
De toute évidence, il suffit de ne considérer que un représentative des classes d'équivalence de la relation d'équivalence "être un complément l'un de l'autre". L'entrée pertinente dans l'OEIS est https://oeis.org/A007869. Incidemment, je suis un peu surpris que là, l'interprétation "classes d'isomorphisme de graphes complets de couleur bord-2 par rapport à la notion évidente d'isomorphisme".(c'est-à-dire permutation des étiquettes de sommets, et permutations des couleurs d'arêtes)" est absente.

enter image description here

Figure 1. Le poset $F_{mathrm{ct}}(1)$. Son ensemble de base est l'ensemble à 1 élément des partitions entières du nombre $1$. Une preuve de l'exactitude de la figure 1 n'est pas donnée ; elle est évidente.

enter image description here

Figure 2. Le non-poset $F_{mathrm{ct}}(2)$. Son ensemble de base est l'ensemble à 2 éléments des partitions entières du nombre $2$. (Je ne sais pas si $n=2$ est le seul nombre pour lequel la relation $F_{mathrm{ct}}(n)$ est non-antisymétrique). Une preuve de l'exactitude de la figure 2 n'est pas donnée ; elle est évidente.

enter image description here

Figure 3. Le poset $F_{mathrm{ct}}(3)$. Son ensemble de base est l'ensemble à 3 éléments des partitions entières du nombre $3$. Une preuve de l'exactitude de la figure 3 n'est pas donnée ; elle est évidente.

enter image description here

Figure 4. Le poset $F_{mathrm{ct}}(4)$. Son ensemble de base est l'ensemble à 5 éléments des partitions entières du nombre $4$. Une preuve de l'exactitude de la figure 3 est constituée par la figure 6.

enter image description here

Figure 5. Le poset $F_{mathrm{ct}}(5)$. Son ensemble de base est l'ensemble à 7 éléments des partitions entières du nombre $5$. Une preuve de l'exactitude de la figure 5 est donnée par la figure 7.

enter image description here

Figure 6. Le poset $F_{mathrm{ct}}(6)$. Son ensemble de base est l'ensemble à 11 éléments des partitions entières du nombre $6$. Une preuve de l'exactitude de la figure 6 est donnée par le tableau correspondant dans le pdf.

Diagrammes de Hasse des posets $F_{mathrm{ct}}(3),dotsc,F_{mathrm{ct}}(6)$.

enter image description here

Figure 7. Diagramme de Hasse du poset $F_{mathrm{ct}}(3)$.

enter image description here

Figure 8. Diagramme de Hasse du poset $F_{mathrm{ct}}(4)$.

enter image description here

Figure 9. Diagramme de Hasse du poset $F_{mathrm{ct}}(5)$.

enter image description here

Figure 10. Diagramme de Hasse du poset $F_{mathrm{ct}}(6)$.

Tableaux avec probabilités conditionnelles par rapport à la distribution uniforme.

enter image description here

Figure 11. Probabilités conditionnelles d'un type de cycle donné d'une permutation de $3$ forçant une permutation d'un autre type de cycle donné.

enter image description here

Figure 12. Probabilités conditionnelles d'un type de cycle donné d'une permutation de $4$ forçant une permutation d'un autre type de cycle donné.

enter image description here

Figure 13. Probabilités conditionnelles d'un type de cycle donné d'une permutation de $5$ forçant une permutation d'un autre type de cycle donné.

enter image description here

Figure 14. Probabilités conditionnelles d'un type de cycle donné d'une permutation de $6$ forçant une permutation d'un autre type de cycle donné.

Tableaux animés prouvant les figures 8, 9, 12, 13.

enter image description here

Figure 6. Gif animé avec lequel on peut déterminer quels types de cycles d'automorphismes sont forcés par d'autres types de cycles d'automorphismes, sur $n=4$ sommets.

enter image description here

Figure 7. Gif animé avec lequel on peut déterminer quels types de cycles d'automorphismes sont forcés par d'autres types de cycles d'automorphismes, sur $n=5$ sommets. La fréquence doit être suffisamment basse pour, si l'on veut vérifier les tableaux, faire facilement des captures d'écran du tableau concerné.

Il semble utile d'épeler les implications codées dans les digraphes ci-dessus sous forme de phrases anglaises.
(Je saute (0) les cas triviaux $nin{1,2}$, (1) les tautologies représentées par les boucles, et (2) la conclusion triviale que tout automorphisme force l'identité-automorphisme) :

$n=3$.

  • Pour tout graphe sur $3$, s'il possède un automorphisme de type cycle $3$, alors il possède un automorphisme de type cycle $2+1$.

$n=4$

  • Pour tout graphe sur $4$, s'il possède un automorphisme de type cycle $4$, alors il possède un automorphisme de type cycle $2+2$.

  • Pour tout graphe sur $4$, s'il possède un automorphisme de type cycle $3+1$, alors il possède un automorphisme de type cycle $2+1+1$.

$n=5$

  • Pour tout graphe sur $5$, s'il possède un automorphisme de type cycle $5$, alors il possède un automorphisme de type cycle $2+2+1$.

  • Pour tout graphe sur $5$, s'il possède un automorphisme de type cycle $4+1$, alors il possède un automorphisme de type cycle $2+2+1$.

  • Pour tout graphe sur $5$, s'il possède un automorphisme de type cycle $3+2$, alors il possède un automorphisme de type cycle $3+1+1$, et un automorphisme de type $2+2+1$, et un automorphisme de type cycle $2+1+1+1$.

  • Pour tout graphe sur $5$, s'il possède un automorphisme de type cycle $3+1+1$, alors il possède un automorphisme de type cycle $2+1+1+1$.

En particulier, les automorphismes de type cycle $3+2$ sont le plus petit exemple d'une symétrie qui force toujours. plus d'un symétries supplémentaires non conjuguées (et là il se trouve qu'il y en a trois : $3+1+1$, $2+2+1$, $2+1+1+1$).

Malheureusement, je ne vois pas de principe régissant les données. J'ai peu d'espoir qu'il y ait une belle loi à découvrir.ed; par exemple, la hauteur des posets $F_{mathrm{ct}}(n)$ n'est pas monotone en $n$.: alors que $F_{mathrm{ct}}(5)$ a une hauteur de $4$, le poset $F_{mathrm{ct}}(6)$ a encore une hauteur de $3$.

Peter et YCor ont déjà donné un contre-exemple, donc cette réponse est juste un commentaire supplémentaire. Je vais ignorer les boucles pour plus de simplicité. Si $varGamma$ est un groupe de permutation sur $lbrace 1,ldots, n rbrace$, alors la 2-fermeture varGamma_2$ de varGamma$ est le plus grand sous-groupe de S_n$ tel que les orbites de varGamma_2$ sur l'ensemble des paires non ordonnées lbrace v,wrbrace$ sont les mêmes que les orbites de varGamma$ sur l'ensemble des paires non ordonnées. Clairement, $varGammalevarGamma_2$. (Google "2-fermeture" et "orbite" pour des tonnes de références et plus d'informations).

Maintenant, l'observation clé est que tout groupe d'automorphisme d'un graphe est 2-clos.ed; c'est-à-dire qu'il est égal à sa propre 2-fermeture. Donc pour trouver des contre-exemples à votre question il suffit de trouver tout $pi_0$ tel que $langle pi_0rangle$ n'est pas 2-clos. L'exemple de YCor est une permutation à un cycle : pour $nge 3$ et $pi_0=(1,2,ldots,n)$, la 2-fermeture de $langle pi_0rangle$ contient également $n$ éléments supplémentaires d'ordre 2 (pensez aux réflexions d'un polygone régulier autour d'une ligne passant par le centre).

(Incidemment, de nombreuses sources définissent "2-fermé" en utilisant des paires ordonnées plutôt que des paires non ordonnées. Pour les graphes non orientés, nous avons besoin de paires non ordonnées).

AJOUTÉ.

Je vais commencer mais pas encore terminer une description complète de l'ensemble $F(n)$ défini par Peter. Pour récapituler : $F(n)$ est l'ensemble de toutes les paires $(pi_0,pi_1)$ de permutations dans $S_n$ telles que tout graphe $G$ à n$-vertex qui a $pi_0$ comme automorphisme a aussi $pi_1$ comme automorphisme. Décrire $F(n)$ revient à décrire les groupes $Gamma_{pi_0}=lbrace pi_1 mid (pi_0,pi_1)in F(n)rbrace$. ($Gamma_{pi_0}$ est un groupe car l'intersection des groupes est un groupe).

Les cas $n=1$ et $n=2$ sont triviaux ainsi que le cas $nge 3, pi_0=(1)$ ; je les laisse au lecteur. Supposons que $nge 3 $ et que $pi_0$ n'est pas l'identité.

Deux évidences, la première par définition la seconde par symétrie :
(1) $langle pi_0$ranglele Gamma_{pi_0}$.
(2) Pour tout $gamma dans S_n$, $Gamma_{pi_0^gamma}=Gamma_{pi_0}^gamma$, où l'exponentiation désigne la conjugaison.
Le fait (2) dit que nous devons seulement nous préoccuper de la structure cyclique de $pi_0$.

Prenons donc $pi_0 dans S_n$ et laissons les cycles $C_1,C_2,ldots,C_k$ de $pi_0$ avoir des longueurs $ell_1ge ell_2gecdotsgeell_k$.

Pour $1le jle k$, soit $D_j$ l'unique groupe diédral de degré $ell_j$ qui contient $C_j$. (Pensez à $C_j$ comme les symétries de rotation d'un $ell_j$-gone régulier et $D_j$ comme le groupe de symétrie complet incluant les réflexions). Pour les petites orbites avec $ell_jle 2$, prenez $D_j=C_j$. Définissons maintenant $Gamma^*_{pi_0}= D_1oplus cdots oplus D_k$. Par un $t$-gon nous entendons un seul sommet si $t=1$, une seule arête si $t=2$ et un cycle (graphique) de longueur $t$ si $tge 3$. Si on insère un $t$-gon dans un $t$-cycle de $pi_0$, on supposera que le $t$-cycle est un automorphisme du $t$-gon.

Lemme 1. $~Gamma_{pi_0}le Gamma^*_{pi_0}$.
Preuve. Pour tout $ell_jge 2$, prenons un graphe avec un $ell_j$-gon dans $C_j$ et des sommets isolés ailleurs. Le groupe d'automorphisme fixe $C_j$ de manière fixe, donc $Gamma_{pi_0}$ le fait aussi. S'il existe des cycles 1, il faut les connecter en un chemin et connecter une extrémité du chemin à un cycle $t$ ($tge 2$) dans lequel on insère un gon $t$. Plus d'arêtes. Le groupe d'automorphisme fixe chacun des 1-cycles, donc $Gamma_{pi_0}$ le fait aussi. Nous avons donc prouvé que $Gamma_{pi_0}$ fixe la partition des cycles de $pi_0$ par cellule. Prenons maintenant un graphe dans lequel $C_j$ contient un $ell_j$-gon pour chaque $j$ et aucune arête supplémentaire. Le sous-groupe de son groupe d'automorphisme qui fixe la partition de cycle de $pi_0$ au sens cellulaire est $Gamma^*_{pi_0}$. Ceci complète la preuve.
$square$

Pour compléter la détermination de $Gamma_{pi_0}$, nous devons déterminer quels éléments de $Gamma^*_{pi_0}$ préservent toutes les jointures possibles entre différents cycles. Ceci est légèrement compliqué car cela dépend de propriétés arithmétiques : le nombre d'arêtes entre $C_i$ et $C_j$ est divisible par le plus petit commun multiple de $ell_i$ et $ell_j$. D'un point de vue positif, la solution pour deux cycles devrait impliquer la solution pour un nombre quelconque de cycles. Je dois réfléchir à la manière de le faire en douceur.

Avis et notes

A la fin de cet article vous pourrez retrouver les notes d'autres chefs de projet, vous pourrez également montrer la vôtre si vous le souhaitez.



Utilisez notre moteur de recherche

Ricerca
Generic filters

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.