Outer Automorphism of S_6

Lemma If $\alpha \in Aut(S_n)$ maps transpositions to transpositions iff it's an inner automorphism.
proof: ($\Leftarrow$) inner automorphisms are done by conjugation which preserves cycle type. ($\Rightarrow$) todo

Lemma If $n \not = 6$ then $Out(S_n) = 1$.
proof: An outer-automorphism must swap transpositions with some other order-2 conjugacy class. First we count cycles of type $2^k 1^{n-2k}$. You have $\binom{n}{n-2k}$ choices of fixed elements for each, then with the $2k$ remaining elements we can permute these in $2k!$ ways before factoring out the order each transposition is written in and the number of ways we order the transpositions $2^k k!$, therefore there are $$f_k^n = \frac{n!}{(2k)! (n-2k)!} \cdot \frac{(2k)!}{2^k k!}$$ cycles of the given type. In particular $f_1^n = \binom{n}{2}$.
For $n > 6, k > 1$ $$f_k^n > \binom{n}{2k} \ge \binom{n}{2}$$ unless $n = 2k$ or $2k+1$ - but in those cases prove these cases cannot occur - so there can be no outer automorphisms. For $n < 6$ do this too.

Theorem $S_6$ has an outer-automorphism.
proof: There are $6$ $S_5$ subgroups as point stabilizers, but from the following diagram we find an $S_5$ that is not a point stabilizer

Permutations of the 5 colors correspond to permutations of the 6 points (which we label 1,2,3,4,5,6 clockwise starting at the top left) $$(\color{red}{\text{red}}\;\color{yellow}{\text{yellow}})=(1\;2)(3\;6)(4\;5)$$ $$(\color{blue}{\text{blue}}\;\color{green}{\text{green}})(\color{red}{\text{red}}\;\color{purple}{\text{purple}}\;\color{yellow}{\text{yellow}})=(1\;2\;3\;4\;5\;6).$$

So we have discovered an exotic $S_5$ inside $S_6$, I do not know why but there are 6 conjugates of it. We will call the action of $S_6$ on these 6 conjugates $\varsigma$.

gap> s5 := Group((1,2)(3,6)(4,5),(1,3,6,5,4));
Group([ (1,2)(3,6)(4,5), (1,3,6,5,4) ])
gap> ex := ConjugateSubgroups(SymmetricGroup(6),s5);
[ Group([ (1,2)(3,6)(4,5), (1,3,6,5,4) ]), 
  Group([ (1,2)(3,5)(4,6), (1,3,5,6,4) ]), 
  Group([ (1,2)(3,6)(4,5), (1,3,6,4,5) ]), 
  Group([ (1,2)(3,4)(5,6), (1,3,4,6,5) ]), 
  Group([ (1,2)(3,5)(4,6), (1,3,5,4,6) ]), 
  Group([ (1,2)(3,4)(5,6), (1,3,4,5,6) ]) ]
gap> Position(ex, ex[1]^(1,2));                     
2
gap> Position(ex, ex[2]^(1,2));
1
gap> Position(ex, ex[3]^(1,2));
4
gap> Position(ex, ex[4]^(1,2));
3
gap> Position(ex, ex[5]^(1,2));
6
gap> Position(ex, ex[6]^(1,2));
5

Note, that $(1\;2)\varsigma = (1\;2)(3\;4)(5\;6)$ means we have an outer automorphism! well, if we have an automorphism:

gap> Position(ex, ex[1]^(1,2,3,4,5,6));
1
gap> Position(ex, ex[2]^(1,2,3,4,5,6));
3
gap> Position(ex, ex[3]^(1,2,3,4,5,6));
2
gap> Position(ex, ex[4]^(1,2,3,4,5,6));
5
gap> Position(ex, ex[5]^(1,2,3,4,5,6));
6
gap> Position(ex, ex[6]^(1,2,3,4,5,6));
4
gap> StructureDescription(Group((1,2)(3,4)(5,6),(2,3)(4,5,6)));  
"S6"

and we do.

• wikipedia/Automorphisms_of_the_symmetric_and_alternating_groups#The_exceptional_outer_automorphism_of_S6 
•  cp4space/outer-automorphism-of-s6