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}$.

Improve this question
$\endgroup$
4
  • $\begingroup$ It's still a Cayley graph. $\endgroup$
    – Sam Hopkins
    Commented 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
    Commented 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$
    – Hugh Denoncourt
    Commented Jul 26, 2020 at 14:21
  • $\begingroup$ Consider adding the tag "coxeter-groups" to this. $\endgroup$
    – Nathan Reading
    Commented Jul 29, 2020 at 2:12

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Sam Hopkins
    Commented 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$
    – Sam Hopkins
    Commented 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$
    – Sam Hopkins
    Commented Jul 25, 2020 at 15:55
  • $\begingroup$ @SamHopkins Ah, yes. Obvious in hindsight. $\endgroup$
    – M. Winter
    Commented Jul 25, 2020 at 16:57

You must log in to answer this question.

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