# Why is there a unique increasing maximal path in any Bruhat interval under any reflection order?

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!)

-
Michael: Many people who might have an answer to your question (myself included) don't remember the details of the increasing-Bruhat-path interpretation of $R$-polynomials and are too lazy to reach for their copy of Bjorner--Brenti to find it. (In my case, it's not just laziness; I'm about 1000 miles away from my office at the moment.) Providing some partial explanation might help you get an answer. –  Alexander Woo Dec 19 '12 at 0:48
Seriously, those armed with the root version of reflection order are not ready to deal with the reflections... I suggest you provide the theorem on the order-preserving bijection between positive roots and reflections. –  Harry H.Y. Huang Dec 22 '12 at 5:36

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.

-
Thank you very much! This is really helpful. –  Michael Zhong Jan 3 at 3:19
Thanks again! This induction can be used for the reflection order corresponding to $w_0=t_1\cdots t_k s_1\cdots s_k$(GTM 231 Exercise 5.20) when $W$ is finite. But for an arbitrary reflection ordering, I am not sure whether this reasoning still works. –  Michael Zhong Jan 8 at 11:37
I agree that if W is not finite, the argument I gave potentially runs into trouble, since nothing guarantees that the process I described will terminate (and thus you might never obtain an increasing path). However, I think an argument like the following should work: among all reflections t such that u < vt <. v (where <. means "is covered by") take the first possible t (wrt the reflection order). Keep doing this. I bet if this wasn't increasing, the existence of an earlier rank 2 replacement would give a contradiction. –  Hugh Thomas Jan 9 at 1:15