Dear All,


I thought the following question might be well-known, but couldn't find anywhere, so decided to ask here:


Let $A$ and $B$ be two generating sets for $S\_n$, consisting of transpositions.


Question: When the Cayley graphs of $S\_n$ with respect to $A$ and $B$ are isomorphic?


Well, if $\Gamma(S\_n,A)$ is isomorphic to $\Gamma(S\_n,B)$, then of course $|A|=|B|$. Is it true that the answer to the question is "whenever $A$ and $B$ are conjugate"?



When Cayley graphs of the symmetric group wrt generating sets of transpositions are isomorphic?
I claim the answer to your question is yes.
This is my first time posting on mathoverflow. I hope my latex goes ok.


Given $\Gamma(S\_n,A)$, build an auxiliary graph $X(\Gamma(S\_n,A))$, with vertex set $\{1,\ldots,n\}$ and two vertices are adjacent if the corresponding involution is in $A$.
Build a second auxiliary graph $Y$ with vertex set the elements of $A$ with an edge between them if they commute.
Note that $Y$ is the complement of the line graph of $X$.


Let $\Gamma\_1=\Gamma(S\_n,A)$ and let $\Gamma\_2=\Gamma(S\_n,B)$.


We have to show that if $\Gamma\_1$ and $\Gamma\_2$ are isomorphic, then so are $X(\Gamma\_1)$ and $X(\Gamma\_2)$. Since $X(\Gamma\_1)$ and $X(\Gamma\_2)$ are connected, they are isomorphic if and only if $Y(\Gamma\_1)$ and $Y(\Gamma\_2)$ are (assuming they have at least 4 vertices, see <http://en.wikipedia.org/wiki/Line_graph#Characterization_and_recognition>). It thus suffices to show that if $\Gamma\_1$ and $\Gamma\_2$ are isomorphic, then so are $Y(\Gamma\_1)$ and $Y(\Gamma\_2)$.


I will do this by showing that, given $\Gamma\_1$ without labels, I can recover $Y(\Gamma\_1)$ uniquely up to conjugacy in $S\_n$.


The crucial observation is that in $\Gamma(S\_n,A)$, an element at distance 2 from the identity is either a 3-cycle or a product of two disjoint transpositions. If it is a product of two distinct transpositions, then there will be exactly two paths of length 2 joining it with the identity (in other words, it will be contained in a unique $4$-cycle with the identity).
If it is a 3-cycle, there will be exactly either one or three paths of length 2 joining it to the identity.


First, label one vertex of $\Gamma\_1$ "1" (think of it as the identity). 
Now, labels the neighbours of 1 with $x\_1,\ldots,x\_k$ (where $k$ is the valency of $\Gamma$).
We think of these as being undetermined transpositions.
By the argument above, $x\_i$ and $x\_j$ commute if and only if they are contained in a unique $4$-cycle with the identity.
We can now construct $Y(\Gamma\_1$), in a unique way up to conjugacy in $S\_n$.


