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"?

  • $\begingroup$ Isomorphic just as abstract graphs, or as graphs colored by the names of the generators? In particular, can I test whether two transpositions $s$ and $t$ commute by following edges labeled $s$, $t$, $s$, $t$ from some starting vertex? $\endgroup$ Mar 24 '12 at 19:37

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$.

  • 1
    $\begingroup$ Nice proof! It might be clearer to write $X$ and $Y$ as functions of $A$, since they can't be obtained directly from $\Gamma$ without its labels. $\endgroup$ Mar 25 '12 at 4:57
  • $\begingroup$ Let me also point out that we don't need the "assuming they have at least 4 vertices" qualifier -- for $X_1$ and $X_2$ to be nonisomorphic, while having isomorphic line graphs, would require one to have 3 vertices and the other to have 4; but this is impossible as by construction they both have $n$ vertices. $\endgroup$ Mar 25 '12 at 9:07
  • $\begingroup$ That's a very beautiful proof! I tried also to do something via the graph $X$, but I didn't know about the the trick with $Y$. Thanks a lot! $\endgroup$
    – Victor
    Mar 26 '12 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.