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](https://math.stackexchange.com/questions/839939/maximal-chain-in-strong-bruhat-order)



maximal chain in (strong) Bruhat order satisfying constraint
Yes. The relation you are imposing between $\pi$ and $\sigma$ is called [weak order](http://en.wikipedia.org/wiki/Weak_order_of_permutations#Weak_order_of_permutations) -- 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.


