1
$\begingroup$

Consider the (strong) Bruhat order, $\leq_B$, on the symmetric group $S_n$. Suppose there are permutations $\pi,\sigma∈S_n$ such that $\pi\geq_B \sigma$. Suppose further that they satisfy the following property: if i precedes j in $\sigma$ written in single line notation, then i precedes j in $\pi$ written in single line notation.

For example, consider $\sigma=532614$ and $\pi=635421$. Then $\pi\geq_B \sigma$ and $\pi$, $\sigma$ satisfy the aforementioned condition. 3 lies ahead of the 2 lies ahead of the 1 in both $\sigma$ and $\pi$. And 6 lies ahead of the 4 and 5 lies ahead of the 4 in both of them.

My question: Does there exist a maximal chain in the Hasse diagram of the Bruhat order from $\sigma$ to $\pi$, say $\sigma\leq_B \sigma_2\leq_B \cdots \leq_B \sigma_k=\pi$ such that $\sigma_i$ and $\sigma$ satisfy the same property as I mentioned earlier, for all $1≤i≤k$.

For example, here is one maximal chain for the earlier example. $532614\leq_B 632514 \leq_B 635214 \leq_B 635241\leq_B 635421$

I have a feeling that some bubble-sortesque algorithm will do it. But I was hoping to find a ready reference as that would save me some trouble of writing out a rigorous proof.

Thanks

Crossposted at math se

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Yes. The relation you are imposing between $\pi$ and $\sigma$ is called weak order -- specifically, you are saying that $\sigma \leq_W \pi$ where $\leq_W$ is weak order. Every maximal weak chain is also a maximal strong chain, so take a maximal weak chain from $\sigma$ to $\pi$ and it wil have the required property.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks a lot for the pointer. But I think the relation that I am imposing is actually the weak order once I look at the inverse of the permutations. If you look at the example I gave, there is no inclusion of inversion sets. In any case, I think you have got me on the right track, and I should indeed be looking at the weak order. Thanks for the help. $\endgroup$
    – user35313
    Commented Jun 22, 2014 at 1:50
  • 2
    $\begingroup$ People talk about "left weak order" and "right weak order". Strong order is symmetric under taking inverses, but the weak orders aren't. $\endgroup$
    – Allen Knutson
    Commented Jun 22, 2014 at 14:08
  • $\begingroup$ Also, not everyone agrees on what the bijection is between maps $[n] \to [n]$ and orderings of $[n]$. In other words, does $312$ means $(1 \mapsto 3, 2 \mapsto 1, 3 \mapsto 2)$ or $(3 \mapsto 1, 1 \mapsto 2, 2 \mapsto 3)$? This will determine whether you have defined left or right weak order. It doesn't matter for your question, though, since inversion is an isomorphism between left and right weak orders. $\endgroup$
    – David E Speyer
    Commented Jun 22, 2014 at 14:11

You must log in to answer this question.