Maximal chain in (strong) Bruhat order

91 Views Asked by At

Consider the (strong) Bruhat order, $\leq_{B}$, on the symmetric group $S_n$. Suppose there are permutations $\pi,\sigma \in 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 $\sigma \geq_{B} \pi$ 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\leq i\leq k$.

For example, here is one maximal chain for the earlier example. $532614 \leq _{B} 632514\leq_{B} \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.