Exercice 12, § 2

Soit $n$ un entier $\geqslant 2$ et soit $p$ un nombre premier $> n/2$. Soit H un sous-groupe de $\mathfrak{S}_n$ qui agit transitivement sur $\{1, . . . , n\}$, contient une transposition et un cycle d’ordre $p$. Soit G un graphe tel que

– L’ensemble de ses sommets est $S =\{1, . . . , n\}$;

– L’ensemble F de ses flèches est l’ensemble des couples $(i, j)\in S\times S$ telles que la transposition $\tau_{i,j}$ appartienne à H ;

– On a $o((i, j)) =i,t((i, j)) =j$ et $(i, j) = (j, i)$ pour tout $(i, j)\in F$. a) Démontrer que toute composante connexe de G est un graphe complet. b) Démontrer que si G est connexe, alors $H =\mathfrak{S}_n$.

c) Démontrer qu’il existe un homomorphisme de groupes de $\mathfrak{S}_n$ dans Aut(G) tel que, pour tout $\sigma \in \mathfrak{S}_n$, l’application Som($\sigma$ ) soit égale à la permutation $\sigma$. Démontrer alors que $\mathfrak{S}_n$ agit transitivement sur l’ensemble des composantes connexes de G, et que celles-ci sont deux à deux isomorphes.

d) Soit $\sigma \in H$ un cycle d’ordre $p$. Démontrer que $\sigma$ stabilise chaque composante connexe de G. En conclure que $H =\mathfrak{S}_n$.