8
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • $\begingroup$ 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. $\endgroup$
    – dhy
    Commented Nov 3, 2018 at 20:09
  • $\begingroup$ @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. $\endgroup$
    – Matt Samuel
    Commented Nov 3, 2018 at 20:10
  • $\begingroup$ 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$. $\endgroup$
    – dhy
    Commented Nov 3, 2018 at 20:18
  • $\begingroup$ @dhy I think I see what you mean. There are at most that many paths to all elements of length $\ell(u) $. $\endgroup$
    – Matt Samuel
    Commented Nov 3, 2018 at 20:37
  • 1
    $\begingroup$ 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." $\endgroup$
    – Timothy Chow
    Commented Nov 3, 2018 at 21:01

1 Answer 1

Reset to default
3
$\begingroup$

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

The cd-index is a noncommutative generating function encoding chain enumeration by ranks. The conjecture would in particular imply that the number of saturated chains is maximized on these dual stacked polytopes.

As far as I know, the conjecture is still wide open.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Bizarre. This is from weeks ago but I never got a notification. $\endgroup$
    – Matt Samuel
    Commented Nov 29, 2018 at 12:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .