Let $(W,S)$ be a Coxeter group with Bruhat order $\leq$ and length function $\ell(w)$.

Definition: a subset $X \subset W$ has the chain property if whenever $x,y \in X$ with $x < y$, there exists $x_0, x_1, \ldots, x_k \in X$ such that $x=x_0 < x_1 < \ldots < x_k = y$, with $\ell(x_i) = \ell(u) + i$.

Remark: clearly, for this property to hold, it is sufficient the existence of a $x_1 \in X$ such that $x < x_1 \leq y$ and $\ell(x_1) = \ell(x) + 1$.

Let $J \subset S$ and consider $W_J$ the parabolic subgroup spanned by $J$. Then the right quotient $W/W_J$ has a system of representatives given by $W^J = \{ w :\, \ell(ws) > \ell(w),\, \forall s \in J \}$ where each $w \in W^J$ is the minimal element of the right coset $w W_J$.

It is well known that the system of representatives $W^J$ of the right coset has the chain property (Theorem 2.5.5 p.45 of Bjorner-Brenti's Combinatorics of Coxeter Groups).

Now let $I,J \subset S$. Then the double quotient $W_I \backslash W / W_J$ has a system of representatives given by $^I W^J = (W^I)^{-1} \cap W^J$ where each $w \in$$^I W^J$ is the minimal element of the double coset $W_I w W_J$ (Proposition 2.7.3 p.64 of Carter's Finite Groups of Lie Type).

My question is then: does the system of representatives $^IW^J$ of the double coset has the chain property?

I am actually interested in this result only in the case of Weyl groups, but it seemed best to ask it in the above generality. This looks like a textbook question but I could not find a reference for this nor did I succeed in adapting the cited Bjorner-Brenti's Theorem to this case.


1 Answer 1


By part (b) of Remark 1.6 on page 7 of http://www.math.lsa.umich.edu/~jrs/papers/affine.ps.gz, the answer seems to be: "Not always"!

A shorter counterexample is $W=S_4$ the symmetric group on 4 letters and $I=J=\{ (12), (34) \}$.

Then $\# W_I=4$ so that $W^I = \left\{ w \in S_4:\, w(1) < w(2),\, w(3) < w(4) \right\}$ has $\# W^I= \# W/W_I = 3! = 6$ which are easy to find by construction. This reduces the work to pin down $^I W^I = (W^I)^{-1} W^I$ which can be computed to be the three permutations $1$, $(23)$, $(13)(24)$.

They have length 0,1 and 4, respectively, which shows that $^I W^I$ does not have the chain property at all!

  • 1
    $\begingroup$ I saw your question and was on my way to find Stembridge's counterexample, but you were too fast for me. :) Stembridge actually says this in part (b) of Remark 1.6 of the same paper. Good question, and good answer. $\endgroup$ Jul 24, 2014 at 13:10
  • $\begingroup$ Thanks @NathanReading! I corrected the reference to Stembridge and gave a shorter counterexample :) Actually, I had googled on the subject before, but I only found Stembridge reference a few minutes after I posted the question here: it is a very nice reference since not all references on Bruhat order deal with the double coset. $\endgroup$
    – Lucas Seco
    Jul 25, 2014 at 3:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.