TITLE: Why is there a unique increasing maximal path in any Bruhat interval under any reflection order?
QUESTION [2 upvotes]: According to the increaing-Bruhat-path-explanation of Kazhdan-Lusztig $R$-polynomials(in fact $\tilde{R}$-polynomials), and the fact that $[q^{l(x,y)}]\tilde{R}_{x,y}(q)=1$, there is a unique increasing maximal path in any Bruhat interval under any reflection order. I wonder if there is any direct explanation.
    Thank Professor Woo for suggesting providing more details. So the following is an detailed description of the increaing-Bruhat-path-explanation of Kazhdan-Lusztig $R$-polynomials, which is from Bjorner and Brenti's book `Combinatorics of Coxeter Groups', GTM 231, pp.136-144.
    Suppose $(W,S)$ is a Coxeter system with $\Phi$ its root system. A total ordering $<$ on $\Phi^+$ is called \textbf{a reflection ordering}, if for all $\alpha,\beta \in \Phi^+$ and $\lambda, \mu >0$ such that $\lambda\alpha+\mu\beta\in \Phi^+$, then $\alpha<\lambda\alpha+\mu\beta<\beta$ or $\alpha>\lambda\alpha+\mu\beta>\beta$.
    Given a Bruhat path $\Delta=(a_0,a_1,\cdots,a_r)$ and a reflection ordering $<$, define $l(q)=r$, $D(\Delta;<)=\{i \in [r-1]: a_{i-1}^{-1}a_i>a_{i}^{-1}a_{i+1}\}$, and $R_<(u,v)=\sum_{\Delta\in B(u,v):D(\Delta,<)=\emptyset}{q^{l(\Delta)}}$, where $u,v\in W$, $B(u,v)$ denotes all Bruhat paths from $u$ to $v$. Then Theorem 5.3.4 in Bjorner and Benti' book shows that $\tilde{R}{u,v}(q)=R_<(u,v)$, where $q^{\frac{1}{2}l(u,v)}\tilde{R}{u,v}(q^{\frac{1}{2}}-q^{-\frac{1}{2}})=R_{u,v}(q)$. (I am sorry about the last two subscripts which I can't correctly write down!)

REPLY [1 votes]: Clearly there is at most one increasing path, so the only problem is to find it.  
Take some path, and suppose it is not increasing.  So there is some length 2 subpath which is not increasing.  Replace it by an increasing path.  The fact that this is possible only requires that you work inside a rank 2 root system.  
Repeat.  We need to check that we can't get caught in an infinite loop.  To do this, we need to make sure that each replacement step can be done in such a way as to reduce some statistic on chains.  For example, we could use lexicographic order on the labels of the chains (using the given reflection order).  
Having written this down, I now realize that this and more is contained in the classic paper by Björner and Wachs introducing CL-shellability: Bruhat order of Coxeter groups and shellability. Adv. in Math. 43 (1982), no. 1, 87–100.
EDIT: Oops.  It's not obvious that there is only one increasing path.  A priori, it could be possible that you could take your fixed word for $v$ and, by removing two different increasing subsequences of reflections, obtain a word for $u$.  
The argument that this doesn't happen, as given in Björner-Wachs, is as follows.  Suppose the result is already established for chains of length less than $\ell(v)-\ell(u)$.  Let $v=s_{1}\dots s_{q}$ be your fixed word for $v$, and suppose that you can remove reflections $s_{i_1}<\dots<s_{i_r}$ or $s_{j_1}<\dots<s_{j_r}$ to get a word for $u$.  Suppose further that $i_r<j_r$.  Let $t$ be the reflection $s_qs_{q-1}\dots s_{j_r}\dots s_{q-1}s_q$.  Then $\ell(ut)<\ell(u)$.  But $ut$ must be the first step up the chain corresponding to the reflections labelled by $j$'s.  Contradiction.  So we must not have $i_r<j_r$.  By symmetry, we can't have $j_r<i_r$.  So $i_r=j_r$, and we have reduced the problem to a shorter interval.
{"set_name": "stack_exchange", "score": 2, "question_id": 116716}