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

Consider the graph $G_n$, with $V(G_n) = S_n$ (the set of permutations of a set of size $n$) and having an edge $\sigma\sigma'$ iif $\sigma'$ can be obtained from $\sigma$ by applying a transposition.

This $G_n$, defined that way, has a "name"?

It seems pretty easy, (and this is the main question) but I'm not sure how $G_n$ "looks like". For instante:

  • $G_1$ is $K_1$
  • $G_2$ is $K_2$
  • $G_3$ is $K_{3,3}$
  • $G_4$ is ??
  • $\dots$
  • $G_n$ is ??
share|cite|improve this question
It's the Cayley graph of $S_n$ with respect to the set of transpositions. Not sure if there is a more concrete name... – darij grinberg Dec 29 '12 at 21:06
Well, but is it easy to see how $G_4$ looks like? – GraphTransposition Dec 29 '12 at 22:34
It's not clear what you are asking? – Chris Godsil Dec 30 '12 at 0:14
I'm asking what should be the "??" in my original question. The graph described when $n = 3$ is the $K_{3,3}$. I wonder what's the graph described on, for instance $n=4$. I'm looking for an answer like $G_4 = K_{8,8,8}$, which is wrong althought $K_{8,8,8}$ has 24 vertices, as expected. – GraphTransposition Dec 30 '12 at 1:31
The graph $G_n$ is the Hasse diagram of the absolute order on $S_n$. This gives some insight into what this graph "looks like." See – Richard Stanley Dec 30 '12 at 2:54

This is the undirected version of the Bruhat graph. To make the graph directed, direct an edge $\sigma \rightarrow \sigma'$ if $\ell(\sigma') > \ell(\sigma)$, where $\ell(\sigma)$ denotes the length of $\sigma$ defined to be the number of inversions of $\sigma$. A related graph is the Hasse diagram of the Bruhat order, which is the subgraph of the Bruhat graph where only the edges $\sigma \rightarrow \sigma'$ with $\ell(\sigma') = \ell(\sigma) + 1$ are kept. A basic fact is that for any edge $\sigma \rightarrow \sigma'$ in the Bruhat graph with $\ell(\sigma') - \ell(\sigma) > 1$, there is a path of edges in the Hasse diagram starting at $\sigma$ and ending at $\sigma'$.

A standard reference for this material is Chapter 2 of Bjorner and Brenti's Combinatorics of Coxeter Groups.

share|cite|improve this answer
Not precisely, because he allows any transpositions, not just $\left(i,i+1\right)$. – darij grinberg Dec 29 '12 at 21:49
@darij grinberg: Only using simple transpositions defines the weak order on S_n, while using all transpositions defines the Bruhat order. – Michael Joyce Dec 29 '12 at 22:02

1) One can say something about the $k$-neighbourhoods of a vertex $v$ (i.e. sets of vertices at distance $k$ from $v$). For $v=()$, the identity element of $S_n$, each $k$-neighbourhood is a union of conjugacy classes of $S_n$.

E.g. for $k=1$ you get $n \choose 2$ vertices, corresponding to involutions of type $2^1$, a.k.a. transpositions $(ab)$, and there are no edges between them. That is, there are no triangles in your graph. By the way this immediately tells you that $K_{888}$ for $G_4$ is very far off.

For $k=2$ you get two types of vertices, namely, the ones corresponding to involutions of type $2^2$, i.e. $(ab)(cd)$, and the ones corresponding to $3$-cycles $(abc)$. This will tell you that for any two vertices at distance 2 there is unique 4-cycle which contains them. Indeed, you can get $(ab)(cd)$ using two transpositions either as $(ab)\cdot (cd)$ or as $(cd)\cdot (ab)$, and you can get $(abc)$ either as $(ac)\cdot (bc)$ or as $(bc)\cdot (ab)$.

2) Another interesting and sometimes useful fact is that the eigenvalues of the adjacency matrix $A$ of $G_n$ can be computed from the values of the irreducible characters of $S_n$; namely, $A$ can be viewed as an element $\sum\limits_{\pi \text{ a transposition}}\pi$ in the center of the group algebra $\mathbb{C}[S_n]$, and the center is generated by such conjugacy class sums; this allows you to simultaneously diagnonalise them, etc.

share|cite|improve this answer

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.