Bruhat order

Definition

If (W, S) is a Coxeter system with generators S, then the Bruhat order is a partial order on the group W. The definition of Bruhat order relies on several other definitions: first, reduced word for an element w of W is a minimum-length expression of w as a product of elements of S, and the length ℓ(w) of w is the length of its reduced words. Then the (strong) Bruhat order is defined by u ≤ v if some substring of some (or every) reduced word for v is a reduced word for u. (Here a substring is not necessarily a consecutive substring.)

There are two other related partial orders:

• the weak left (Bruhat) order is defined by u ≤_L v if some final substring of some reduced word for v is a reduced word for u, and
• the weak right (Bruhat) order is defined by u ≤_R v if some initial substring of some reduced word for v is a reduced word for u.

For more on the weak orders, see the article Weak order of permutations.

Bruhat graph

The Bruhat graph is a directed graph related to the (strong) Bruhat order. The vertex set is the set of elements of the Coxeter group and the edge set consists of directed edges (u, v) whenever u = tv for some reflection t and ℓ(u) < ℓ(v). One may view the graph as an edge-labeled directed graph with edge labels coming from the set of reflections. (One could also define the Bruhat graph using multiplication on the right; as graphs, the resulting objects are isomorphic, but the edge labelings are different.)

The strong Bruhat order on the symmetric group (permutations) has Möbius function given by ${\displaystyle \mu (\pi ,\sigma )=(-1{)}^{\ell (\sigma )-\ell (\pi )}}$, and thus this poset is Eulerian, meaning its Möbius function is produced by the rank function on the poset.