Definition Strong Bruhat order
✓ definition formalized

Strong Bruhat order

The strong Bruhat order is the reflexive transitive closure of Upward reflection edges. Thus \(x\le y\) means that a finite sequence of upward reflection edges joins \(x\) to \(y\), with the empty sequence allowed.

Length strictly increases along every nontrivial edge. Consequently \(x\le y\) implies \(\ell(x)\le\ell(y)\), and \(x\le y\le x\) forces \(x=y\). Together with reflexivity and transitivity, this gives a partial order.

The first nontrivial example

Take \(W=S_3\), with \(s=(12)\) and \(t=(23)\). The interval from the identity to \(w_0=sts=tst\) has ranks \[ \{1\},\quad \{s,t\},\quad\{st,ts\},\quad\{w_0\}. \] Each element in either middle rank is connected by covers to both elements in the adjacent rank where applicable.

The strong reflection graph contains more information than the Hasse diagram initially displays. In particular, \(w_0\) itself is a reflection, so \(1\to w_0\) is an edge of length difference three. It is not a cover. This distinction explains the graph-reconstruction step: an abstract interval first gives covers, whereas the local sheaf comparisons use every reflection edge.

A reduced subword is also different from a prefix. The word \(st\) occurs as a subword of \(sts\), and so does \(ts\), using its last two positions. Bruhat order retains all these subword relations; weak order would only track the appropriate prefix or suffix relations.

References

1. Introduction and conventions.

Lean formalization

OAI.KLInvariance.BruhatLE: Model.lean:18.

OAI.KLInvariance.bruhat_antisymm: Bruhat.lean:38.

Used by