MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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? – David Speyer Mar 24 '12 at 19:37
up vote 8 down vote accepted

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

share|cite|improve this answer
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. – Brendan McKay Mar 25 '12 at 4:57
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. – Harry Altman Mar 25 '12 at 9:07
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! – Victor Mar 26 '12 at 7:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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