5
$\begingroup$

The weak Bruhat graph (or 1-skeleton of the permutohedron) $B_n$ can be constructed as follows:

  • the vertices of $B_n$ are the permutations of the tuple $(1,...,n)$, two are joined by an edge, if they can be transformed into each other by a transposition of two neighboring numbers, e.g.

$$(5,3,\underline{\smash{4,1}},2) \quad\mapsto \quad (5,3,\underline{\smash{1,4}},2).$$

Now, consider the graph $X_n$, basically defined in the same way, but also allowing the "cyclic transposition":

  • the vertices of $X_n$ are the permutations of the tuple $(1,...,n)$, two are joined by an edge, if they can be transformed into each other by a transposition of two neighboring numbers, or the first and the last number, i.e.

$$(\underline 5,3,4,1,\underline 2) \quad\mapsto \quad (\underline 2,3,4,1,\underline 5).$$

Question: Is there a name for the graph $X_n$ in the literature, and what is it used for?

$B_n$ is a spanning subgraph of $X_n$. In fact, $B_n$ can be obtained from $X_n$ by deleting a matching. In contrast to the Bruhat graph, $X_n$ is always arc-transitive. It has $n!$ vertices and degree $n$ (if $n\ge 3$). For example, $X_3=K_{3,3}$.

$\endgroup$
4
  • $\begingroup$ It's still a Cayley graph. $\endgroup$ Jul 24, 2020 at 23:58
  • $\begingroup$ Hmm, $X_n$ is in some way (which I don't know) to $B_n$ as the affine Dynkin diagram $\widetilde A_n$ is to $A_n$ itself …. $\endgroup$
    – LSpice
    Jul 25, 2020 at 1:10
  • $\begingroup$ It can be obtained as a quotient of the weak order graph of $\tilde{A_n}$. Regard each $w \in \tilde{A_n}$ as an affine permutation with window $[w(1),\ldots,w(n)]$. Express each $w(i)$ as $n\cdot q_i + r_i$. Then $\sigma = (r_1,\ldots,r_n)$ is a permutation. The effect of an ordinary $A_n$ generator is to swap adjacent values in $\sigma$. The affine generator swaps the values $1$ and $n$. Quotient by relating affine permutations that have the same permutation of remainders. See Bj$\ddot{\text{o}}$rner and Brenti's "Affine Permutations of Type A", Section 3, for some of the details. $\endgroup$ Jul 26, 2020 at 14:21
  • $\begingroup$ Consider adding the tag "coxeter-groups" to this. $\endgroup$ Jul 29, 2020 at 2:12

1 Answer 1

6
$\begingroup$

A Markov chain on the symmetric group with this transition graph (but with directed edges and weights) was investigated by Lam and Williams. This has since received considerable attention, and has been connected to "TASEP on a ring" if you are looking for search words (it doesn't appear that the graph itself has a name in this context).

I should point out that one should not give this graph the tempting names "circular Bruhat graph" or "cyclic Bruhat graph" as both of these have been used to refer to the graph underlying Postnikov's circular Bruhat order, which is different.

$\endgroup$
4
  • 2
    $\begingroup$ Regarding the last paragraph, I would even suggest that 'Bruthat graph' is a bad name for the graph $B_n$. "Permutohedral graph" or something similar would be better. $\endgroup$ Jul 25, 2020 at 14:23
  • 1
    $\begingroup$ I would think 'Bruhat graph' refers to this: en.wikipedia.org/wiki/Bruhat_order#Bruhat_graph $\endgroup$ Jul 25, 2020 at 14:26
  • $\begingroup$ @M.Winter: no, "reflections" would be all transpositions. The adjacent transpositions correspond to what are called "simple reflections." $\endgroup$ Jul 25, 2020 at 15:55
  • $\begingroup$ @SamHopkins Ah, yes. Obvious in hindsight. $\endgroup$
    – M. Winter
    Jul 25, 2020 at 16:57

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.