4
$\begingroup$

Let $\mathbb{S}_m$ the symmetric group on $m$ letters. Let $v\in\mathbb{S}_m$, and consider paths in the Bruhat order like this: $1\lessdot v_1\lessdot\cdots\lessdot v$, where $\lessdot$ means the covering relation in the (strong) Bruhat order. Let $N_v$ be the number of such paths.

It is intuitively clear that $N_v\leq\ell(v)!$ (for a proof, I found just now the reference), and further that the difference $\ell(v)!-N_v$ is even. Can you prove the latter fact?

Remark. What I said should be true for every finite Coxeter group but I am mostly interested in the symmetric group for now.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ For the benefit of people finding this question later: Depending on what definition you have seen of the Bruhat order, it might not be "intuitively clear that $N_v\le\ell(v)!$". But this becomes clear when you know the subword characterization of Bruhat order. See, for example, Björner and Brenti's book "Combinatorics of Coxeter Groups", Theorem 2.2.2. $\endgroup$
    – Nathan Reading
    Commented Jul 31, 2020 at 11:24

1 Answer 1

Reset to default
8
$\begingroup$

$\ell(v)!$ is of course even if $\ell(v)>1$, so the statement is really that $N_v$ is even for $\ell(v)>1$. We find a fixed-point free involution on the set of such Bruhat paths. Suppose that $v_2,v_3,\ldots$ are fixed. By the diamond property of Bruhat order there are exactly two possibilities for $v_1$. This gives the involution we want (in fact many of them).

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ In fact, this argument gives that for any Coxeter group (or even any Eulerian poset) $N_v$ is divisible by $2^{\lfloor \ell(v)/2\rfloor}$. $\endgroup$
    – Richard Stanley
    Commented Jul 31, 2020 at 14:52

You must log in to answer this question.

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