Exercise 12, § 2

Soit $n$ an integer $\geqslant 2$ and let $p$ be a prime number $> n/2$. Let H be a subgroup of $\mathfrak{S}_n$ which acts transitively on ${1, . . . , n}$, contains a transposition and a cycle of order $p$. Let G be a graph such that

– The set of its vertices is $S ={1, . . . , n}$;

– The set F of its arrows is the set of pairs $(i, j)\in S\times S$ such that the transposition $\tau_{i,j}$ belongs to H ;

– We have $o((i, j)) =i,t((i, j)) =j$ and $(i, j) = (j, i)$ for every $(i, j)\in F$. a) Prove that every connected component of G is a complete graph. b) Prove that if G is connected, then $H =\mathfrak{S}_n$.

c) Prove that there exists a group homomorphism of $\mathfrak{S}_n$ into Aut(G) such that, for every $\sigma \in \mathfrak{S}_n$, the mapping Som($\sigma$ ) is equal to the permutation $\sigma$. Prove then that $\mathfrak{S}_n$ acts transitively on the set of connected components of G, and that these are pairwise isomorphic.

d) Let $\sigma \in H$ be a cycle of order $p$. Prove that $\sigma$ stabilizes each connected component of G. Conclude that $H =\mathfrak{S}_n$.