## When Cayley graphs of the symmetric group wrt generating sets of transpositions are isomorphic?

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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

-

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 2012 at 19:37

## 1 Answer

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
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 2012 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 2012 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 2012 at 7:38
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 62, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9462213516235352, "perplexity_flag": "head"}