Orders on Coxeter Groups — with a Problem Set!

John Mangual asks:

So, David, how do weak order and bruhat order work on the permutation group, S_n ? As I understand, Coxeter groups are (finitely generated?) reflection groups and your description of a particular element depends on your choice of presentation. These two orders have to do with the length of the “reduced” word representing a particular element. I still don’t totally get how this works. Also, do they form a distributive lattice under these orders?

That’s a great question, but I have a talk and two papers to work on (and at least one of my coauthors is reading this blog!) So I’ll make it a problem set. If you want to work out the case of weak order on S_n for yourself, read on, then join in in the comments!

There are several different orders people like to consider on Coxeter groups. I will discuss the two most important, called weak order and strong order. Weak order is a lattice, but not a distributive lattice. Strong order is not a lattice. Strong order is also sometimes called “Bruhat order”, and weak order is also sometimes called “weak Bruhat order”.

A Coxeter group is a group generated by a set S. The theory permits S to be infinite, but in the examples of interest it is usually finite. The relations are s^2 = e, for each s \in S, and (st)^{m_{st}} = e, for each (s,t)\in S^2, where m_{st} is an integer depending on the pair (s,t). For now, I’ll ignore the questions about the relation to reflection groups.

The most basic Coxeter group is the symmetric group S_n, with generators s_1 = (1 2), s_2 = (2 3), …, s_{n-1} = (n-1 \ n). To be completely exlicit, s_i switches i and i+1 and leaves the other elements of \{ 1,2, \ldots, n \} fixed.

Given w in W, the length \ell(w) of w is the shortest expression for w in terms of the elements of S. An expression which achieves this shortest length is called reduced. Exercise: for w \in W and s \in S, we always have \ell(ws)=\ell(w) \pm 1.

In strong order, u \leq w if there is a reduced word for u which occurs as a subword of a reduced word for w. (Equivalently, if any reduced word for w contains a reduced subword with product u.)

In weak order, u \leq w if there is a reduced word for u which occurs as a prefix of a reduced word for w. This is a more restrictive condition than the one for strong order, so there are few relations in weak order. Exercise: for w \in W and s \in S, we must either have ws < w or w < ws in weak order. Weak order relations of the form u < us are called covers; and the covers generate all relations.

Weak order is a lattice, but not distributive. Strong order is not a lattice.

Now that you have the definitions, here’s the problem set!

(1) Write down all the elements of S_3, all of the reduced words for each of these elements, and draw weak and strong order on S_3.

(2) In the group S_n, give a concrete formula for \ell(w). Hint: there is exactly one element of S_n which has length {0}, and exactly one which has length \binom{n}{2}; all others are in between. Your formula should have this property as well.

(3) For w \in S_n give a criterion for when \ell(w) = \ell(w s_i)+1
and when \ell(w) = \ell(w s_i)-1.

(4) Describe weak order on S_n.

I can’t think how to write a similar problem set for strong order right now, but I’ll try to come up with one later (or just write up the answer, if I fail.)

Of course, collaberation is encouraged. If you know the answers, though, don’t give them away!

10 thoughts on “Orders on Coxeter Groups — with a Problem Set!”

  1. Pingback: 0xDE ~
  2. Pingback: Annotating Kimmo Eriksson’s Poem « Combinatorics and more ~

  5. Aargh! One last time! Otherwise you’ll have to read my mind!

    You wrote “w.s < w or w >= w.s”. I think you meant “w.s <= w or w <= w.s”.

  9. Let me add to David’s problem set for strong Bruhat order…

    3′)
    a) Describe all t\in S_n such that there exist v,w\in S_n with \ell(vt)=\ell(w)-1 and v<w.
    b) Show that for all t\in S_n found in (a) and all w\in S_n, either wt<w or w<wt.
    c) For w\in S_n and t as in (a), give a criterion for when wt<w, and a criterion for when \ell(wt)=\ell(w)-1. (Bonus: Find a formula for \ell(wt)-\ell(w).)

    4) Describe Bruhat order on S_n.

    I fixed some of Alex’s formulas. David

Comments are closed.