3
$\begingroup$

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 ??
Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ It's the Cayley graph of $S_n$ with respect to the set of transpositions. Not sure if there is a more concrete name... $\endgroup$
    – darij grinberg
    Dec 29, 2012 at 21:06
  • $\begingroup$ Well, but is it easy to see how $G_4$ looks like? $\endgroup$
    – GraphTransposition
    Dec 29, 2012 at 22:34
  • $\begingroup$ It's not clear what you are asking? $\endgroup$
    – Chris Godsil
    Dec 30, 2012 at 0:14
  • $\begingroup$ 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. $\endgroup$
    – GraphTransposition
    Dec 30, 2012 at 1:31
  • 1
    $\begingroup$ 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 arxiv.org/pdf/0706.1405v2.pdf. $\endgroup$
    – Richard Stanley
    Dec 30, 2012 at 2:54

2 Answers 2

Reset to default
2
$\begingroup$

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.

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

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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