An Example of Outer Automorphism of $S_6$ with order 2? This might seem trivial to some ...
But I can't seem to find an outer automorphism of $S_6$ with order $2$. Can someone think of an example?
 A: Isaacs's treatment is memorable for me. $S_5$ has $6$ Sylow $5$-subgroups. The conjugation action here yields a homomorphism $S_5 \rightarrow S_6$ which has to be injective (noting $A_5$ is an impossibly large kernel for this action). This is already strange, as we have obtained a subgroup $H \leq S_6$ isomorphic to $S_5$, acting transitively on the 6 letters.
Next, consider the action of $S_6$ on the left cosets of $H$. This action gives a homomorphism $\sigma: S_6 \rightarrow S_6$ which also has to be injective, hence bijective. Here, the inverse $\sigma^{-1}$  maps the stabilizer of a single letter (one of the "usual" $S_5$'s in $S_6$) to the subgroup $H$ which is transitive. But conjugation takes a point stabilizer to another. Hence $\sigma ^{-1}$ can't be an inner automorphism.
I am not sure if it is easy to see that $\sigma^2$ is inner. The inner automorphisms having index $ \leq 2$ inside the full automorphism group should be doable the same way one shows there are no outer automorphisms in other symmetric groups, with a conjugacy class counting.
Possibly helpful note: A further natural question is whether it is possible to choose the automorphism $\sigma \in {\rm Aut}(S_6) -{\rm Inn}(S_6)$ itself to have order 2, instead of just its image in ${\rm Out}(S_6) :={\rm Aut}(S_6)/{\rm Inn}(S_6) \cong C_2$. The answer to that is yes, addressed in another post here.
A: For some reason I decided to worry about this.  I'm pretty sure there are 36 distinct non-inner automorphisms of $S_6$ of order 2.  One such is $\psi$, given explicitly by the formulas:
$$(1\;2\;3\;4\;5)\to (1\;2\;3\;4\;5),\qquad (1\;6)\to(1\;6)(2\;5)(3\;4). $$
Note that these imply $(x\;6)\to (x\;6)(x+1\;x-1)(x+2\;x-2)$, where "$x\pm \epsilon$" is interpreted mod 5.  It's pretty easy to compute $\psi$ on any element of $S_6$ using this.  For instance, you can show that $\psi$ has order 2 by computing it on all 2-cycles: it turns out that $(x\;y)$ appears in the cycle decomposition of $\psi((a\;b))$ iff $(a\;b)$ appears in the cycle decomposition of $\psi((x\;y))$.
The fixed set of $\psi$ in $S_6$ is $N=$ the normalizer of the subgroup generated by $\sigma=(1\;2\;3\;4\;5)$, which has order 20.  The conjugates of $\psi$ in $\mathrm{Aut}(S_6)$ are in bijective correspondence with the set of 5-Sylow subgroups of $S_6$: $\mathrm{conj}_g\circ \psi\circ \mathrm{conj}_{g^{-1}}$ fixes $g\sigma g^{-1}$.
I don't know a great way to show that these are all the non-inner automorphisms of order 2, other than by computing stuff. The element  $\mathrm{conj}_g\circ \psi$ with $g\in S_6$ is order 2 iff $\psi(g)=g^{-1}$, so you just have to solve for all these: it helps that you can exclude some conjugacy classes right away, since outer automorphisms switch the classes $2^1\leftrightarrow 2^3$, $3^1\leftrightarrow 3^2$, and $6^1\leftrightarrow 3^12^1$.  Aside from the identity, there are 20 elements of type $5^1$, 10 elements of type $4^12^1$, $0$ elements of type $4^1$, and 5 elements of type $2^2$ which satisfy $\psi(g)=g^{-1}$.
(If $g$ is of order 2, then $\psi(g)=g^{-1}$ implies $\psi(g)=g$.  So the 5 elements of type $2^2$ are the ones in $N$.  This means there are at most 10 elements in each of the types $4^1$ and $4^12^1$ with $\psi(g)=g^{-1}$, since these square to elements of type $2^2$.  But the 10 "squareroots" $g$ in $4^1$ of these 5 in $2^2$ are actually in $N$, so are fixed by $\psi$.  For elements of order 5, it helps to notice that the 36 distinct normalizers of 5-Sylow subgroups in $S_6$ have the form $F_i\cap \psi(F_j)$, where $F_k=\{g\in S_6\;|\; g(k)=k\}$ and $i,j\in\{1,\dots,6\}$.  Thus  if $g$ has order 5, $\psi(g)=g^{\pm1}$ implies $g\in F_i\cap \psi(F_i)$ for some $i=1,\dots,6$.)
(Note: the article by Janusz and Rotman (AMM, 1982) was somewhat helpful here, though also annoying: by making some choices they explicitly construct a non-inner automorphism $\phi$ and give lots of explicit formulas for it. However $\phi$ does not have order 2.  Then they deduce a non-inner automorphism $\psi$ of order 2, but don't give many explicit formulas for that.  But in fact a slight perturbation of their original choices leads to $\psi$ directly. I suspect a lot of this stuff is in Lam and Leep (Expositiones Mathematicae, 1993), but that paper is not accessible to me.)
