4
$\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
    Commented Dec 29, 2012 at 21:06
  • $\begingroup$ Well, but is it easy to see how $G_4$ looks like? $\endgroup$
    – GraphTransposition
    Commented Dec 29, 2012 at 22:34
  • $\begingroup$ It's not clear what you are asking? $\endgroup$
    – Chris Godsil
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .