Solution (source code)

= Solution

First determine when a <group automorphism> can carry a <transposition> to another type of <involution>. An <involution> in $S_n$ is a product of $k$ disjoint <transpositions>, and its <conjugacy class> has size
$$
\frac{n!}{2^k k!(n-2k)!}.
$$
An automorphism preserves element orders and conjugacy-class sizes. Equality with the transposition-class size $n(n-1)/2$ requires
$$
\frac{(n-2)!}{(n-2k)!}=2^{k-1}k!.
$$
For $k=2$ this says $(n-2)(n-3)=4$, which has no integral solution $n\ge4$. For $k=3$, the minimum value of the left side, at $n=6$, is $4!=24=2^2\cdot3!$; it increases strictly for larger $n$. For $k\ge4$, even its minimum $(2k-2)!$ exceeds $2^{k-1}k!$: at $k=4$ this is $720>192$, and the ratio of these two quantities increases at the next step by $(2k)(2k-1)/(2(k+1))>1$. Thus only in degree six can the <transposition> class be exchanged with a different <involution> class, namely the triple <transpositions>.

We next prove that any automorphism preserving <transpositions> is an <inner automorphism>. Regard a <transposition> as an edge of the <complete graph> on the $n$ letters. Two distinct <transpositions> fail to commute exactly when their edges meet. Any family of pairwise intersecting edges is contained in a vertex star or a triangle: after choosing $\{a,b\}$ and $\{a,c\}$, an edge not containing $a$ must be $\{b,c\}$, which precludes any fourth edge. For $n\ge5$, the stars are therefore distinguished as the maximal such families of size $n-1\ge4$. An automorphism permutes stars, inducing a permutation $\pi$ of the letters; their pairwise intersections show that $(i\ j)$ is sent to $(\pi(i)\ \pi(j))$. Since <transpositions> generate $S_n$, this is conjugation by a permutation.

For $n=4$, stars and triangles both have three edges, but a star generates $S_4$ while a triangle generates a subgroup $S_3$. An automorphism preserves the order of the generated subgroup and hence still distinguishes stars. For $n=3$, every permutation of the three <transpositions> is induced by conjugation in $S_3$, since its conjugation action on them is faithful and has order six. The groups $S_1,S_2$ have trivial automorphism groups. This completes the small cases.

It follows that all automorphisms for $n\ne6$ are inner. In degree six, an automorphism permutes the two <involution> classes of size 15; the kernel of this action consists precisely of the inner automorphisms. Therefore the <automorphisms of the symmetric group> satisfy
$$
\boxed{\operatorname{Out}(S_n)=1\ (n\ne6),\qquad |\operatorname{Out}(S_6)|\le2.}
$$