Does every automorphism of a permutation group preserve cycle structure? In class we proved that the conjugacy map preserves cycle structure, and I was wondering if this was the case for any automorphism of a permutation group.
I intuitively think that it should be the case, because automorphisms are isomorphisms from a group to itself and isomorphisms should not modify any fundamental structure of an element (i.e. generators must map to generators, an element of a certain power is mapped to one of the same power etc..). However, I don't have any actual reason to think that cycle structure is a fundamental property of an element of a permutation group, and I'm struggling to prove the assertion in the general case.
Anyone have any ideas or insights?
 A: Considering joriki's comment, I'll interpret 'permutation group' as meaning 'symmetric group', because otherwise it is obvious that cycle structure isn't preserved; the permutation group
$$V:=\{\operatorname{id}_{S_4},(1\ 2),(3\ 4),(1\ 2)(3\ 4)\}\subset S_4,$$
has many automorphisms that do not preserve cycle structure, for example.

First some terminology: An inner automorphism of a group $G$ is a $\varphi\in\operatorname{Aut}(G)$ for which
$$\exists x\in G:\ \forall g\in G:\qquad \varphi(g)=xgx^{-1}.$$
That is, the automorphism $\varphi$ is given by conjugation by $x\in G$. Automorphisms that are not inner are called outer automorphisms. It is a nice and instructive exercise to check that the inner automorphisms form a normal subgroup $\operatorname{Inn}(G)\unlhd\operatorname{Aut}(G)$.
For symmetric groups conjugation preserves cycle structure, as you proved in class. Put briefly, conjugating a $g\in S_n$ by some permutation $x\in S_n$ simply permutes the numbers in any cycle representation of $g$ by the permutation $x$, so this preserves the cycle structure. That is to say,
$$\text{ If }\qquad g(i)=j\qquad \text{ then }\qquad (xgx^{-1})(x(i))=x(j).$$ 
This means all inner automorphisms of $S_n$ preserve cycle structure. 
It is a weird and nontrivial fact that all automorphisms of all symmetric groups are inner automorphisms, except for some automorphisms of $S_6$. These outer automorphisms do not preserve cycle structure. You can check this by looking at explicit outer automorphisms of $S_6$. User 2015's answer gives a construction for such automorphisms, and google will give you many more constructions, for example here and here.
I don't know of a simple proof of the fact that all automorphisms of $S_n$ are inner for $n\neq6$, but here is a nice and elegant proof by user anon using only basic group theory and combinatorics.
A: Consider $S_5$. Let $\sigma$ be a $5$-cycle in $S_5$.
Check that if $$N=N_{S_5}(<\sigma>)$$ then $$\mid N\mid=20$$(You can use the formula that for $p$-cycle, $\sigma$, $N_{S_p}(<\sigma>)=p(p-1)$). Now consider $$\phi:S_5\longrightarrow T(S_5/N)\cong S_6$$ by the obvious group action where $S_5/N$ is set of $6$ distinct left cosets of $N$ in $S_5$. Now $ker\phi$ is the largest normal subgroup of $S_5$ contained in $N$. Since $N$ has order $20$ and the normal subgroup of $S_5$ are only $A_5$ and $e$, hence the map $\phi$ is injective. Let us denote $Im(\phi)$ as $H$. Note that $H$ is a transitive subgroup of $S_6$ as $$\phi(yx^{-1})(xN)=yN.$$  Now consider the map$$\psi:S_6\longrightarrow T(S_6/H)\cong S_6$$ coming from the group action on the set $S_6/H$ of $6$ elements. From the similar reasoning as above you can prove that $\psi$ is also injective and hence surjective and so it is an isomorphism. But note that for $\alpha\in\psi(H)$, $\alpha$ fixes the coset $H$. Hence $\psi(H)$ is not a transitive subgroup. But every inner automorphism takes transitive subgroup to a transitive subgroup. Hence $\psi$ is not inner. So, $\psi$ does not preserve the cycle structure.
