# How many maximal length Bruhat paths from $u$ to $w$ can there be?

I've been doing some work with saturated Bruhat paths in a Coxeter group between two elements $$u\leq w$$. It seems to me that if $$\ell(u) =0$$, then there are at most $$\ell(w)!$$. I haven't tried to prove this, it's more of an empirical observation. (Now that I think about it, it's pretty easy to prove, because if you fix a reduced word a downward path is uniquely determined by the deletion order of the letters in the word.)

Taking this as a given, if $$\ell(u)>1$$ there should be fewer than $$\ell(w)!$$ paths, but I've noticed it's possible that there are more than $$(\ell(w) - \ell(u))!$$. Is there a known (or easily knowable) bound for the number of paths from $$u$$ to $$w$$ that involves $$\ell(u)$$?

Let's restrict to finite groups, because I'm aware short Bruhat intervals can be large in infinite groups. This doesn't preclude the possibility of the kind of bound I'm asking for, but I'm more interested in finite groups anyway and I would guess we can do better in that case.

• A quick note: The same argument that you use in the $\ell(u)=0$ case gives a bound of $\ell(w)(\ell(w)-1)\cdots(\ell(u)+1)$ in general.
– dhy
Nov 3, 2018 at 20:09
• @dhy I don't think so, because there may be more than one subword for $u$. You would have to do something like multiply by the number of distinct subwords. Nov 3, 2018 at 20:10
• I think the bound still applies - your objection implies that a stronger argument for a $(\ell(w)-\ell(u))!$ bound fails, but my bound only needs to fix an ordering for $w$ and not a distinguished subword corresponding to $u$.
– dhy
Nov 3, 2018 at 20:18
• @dhy I think I see what you mean. There are at most that many paths to all elements of length $\ell(u)$. Nov 3, 2018 at 20:37
• This may not answer your question, but there may be some useful information in John Stembridge's paper, "A weighted enumeration of maximal chains in the Bruhat order." Nov 3, 2018 at 21:01

If you'll allow me to ignore the restriction to finite groups, there is a conjectured upper bound, phrased in terms of polytopes, depending on both $$\ell(u)$$ and $$\ell(w)$$: Conjecture 7.3 of the paper "The cd-index of Bruhat intervals" (Electronic journal of combinatorics 11 (2004), #R74) is that the cd-index is maximized on certain intervals that are isomorphic to "dual stacked polytopes". (If this is the maximum, it is attained: see Proposition 7.2 of the same paper.)