In der Mathematik ist die Bruhat-Ordnung eine Halbordnung auf einer Coxeter-Gruppe und der Bruhat-Graph ein zur Bruhat-Ordnung assoziierter gerichteter Graph. (Die Bruhat-Ordnung ist der transitive Abschluss der Kantenrelation.)

Sei ${\displaystyle (W,S)}$ ein Coxeter-System, d. h. eine Coxeter-Gruppe ${\displaystyle W=\langle r_{1},\ldots ,r_{n}\mid (r_{i}r_{j})^{m_{ij}}=1\rangle }$ mit Erzeugern ${\displaystyle S=\left\{r_{1},\ldots ,r_{n}\right\}}$. Für ${\displaystyle w\in W}$ ist ein reduziertes Wort ein Ausdruck minimaler Länge in Erzeugern aus ${\displaystyle S}$ und ${\displaystyle l(w)}$ die Länge eines reduzierten Wortes.

Die Bruhat-Ordnung ist die auf ${\displaystyle W}$ durch

${\displaystyle w_{1}\leq w_{2}\Longleftrightarrow {\mbox{ ein Teilstring eines reduzierten Wortes für }}w_{2}{\mbox{ ist ein reduziertes Wort für }}w_{1}}$

definierte Halbordnung.

Der Bruhat-Graph ist der Graph mit Knotenmenge ${\displaystyle W}$, in dem es genau dann eine gerichtete Kante von ${\displaystyle w_{1}}$ und ${\displaystyle w_{2}}$ gibt, wenn ${\displaystyle w_{1}w_{2}^{-1}}$ eine "Spiegelung", d. h. von der Form ${\displaystyle w_{1}w_{2}^{-1}=wsw^{-1}}$ mit ${\displaystyle w\in W,s\in S}$, und ${\displaystyle l(w_{1})<l(w_{2})}$ ist.

Die Ordnung macht ${\displaystyle (W,\leq )}$ zu einer halbgeordneten Menge. Die Relation erfüllt eine Form der Hochhebungseigenschaft: Ist ${\displaystyle u\leq w}$ für zwei Elemente aus ${\displaystyle W}$ und existiert ${\displaystyle s\in S}$ mit ${\displaystyle sw\leq w}$ und ${\displaystyle u\leq su}$ so gilt auch ${\displaystyle su\leq w}$ und ${\displaystyle u\leq sw}$. Mit dieser Eigenschaft lässt sich zeigen, dass es in endlichen Coxetergruppen immer ein eindeutiges größtes Element bzgl. der Bruhat-Ordnung gibt. Dieses Element ist aufgrund seiner Eindeutigkeit automatisch selbstinvers.

Weiterhin erfüllt die Ordnung auch die Kettenbedingung: Ist ${\displaystyle u\leq w}$ so existiert eine Kette ${\displaystyle u=v_{0}\leq v_{1}\leq \dots \leq v_{n}=w}$ mit der Eigenschaft ${\displaystyle l(v_{i})=l(u)+i}$ für alle ${\displaystyle i=1,\dots ,n}$.

Für Coxetersysteme lassen sich ebenfalls zwei weitere Halbordnungen definieren. Einerseits die schwache Rechtsordnung:

${\displaystyle w_{1}\leq _{R}w_{2}\Longleftrightarrow \exists n\in \mathbb {N} ,s_{1},\dots ,s_{n}\in S:w_{2}=w_{1}s_{1}\dots s_{n}{\text{ und }}l(w_{1}s_{1}\dots s_{i})=l(w_{1})+i{\text{ }}\forall i=1\dots n}$

Und analog die schwache Linksordnung:

${\displaystyle w_{1}\leq _{L}w_{2}\Longleftrightarrow \exists n\in \mathbb {N} ,s_{1},\dots ,s_{n}\in S:w_{2}=s_{1}\dots s_{n}w_{1}{\text{ und }}l(s_{1}\dots s_{i}w_{1})=l(w_{1})+i{\text{ }}\forall i=1\dots n}$

Wie die Bruhat-Ordnung lassen sich auch diese beiden Ordnungen durch Teilwortbedingungen beschreiben. In der schwachen Rechtsordnung ist ${\displaystyle w_{1}}$ kleiner oder gleich ${\displaystyle w_{2}}$ genau dann wenn es eine reduzierte Darstellung von ${\displaystyle w_{2}}$ gibt die mit einer reduzierten Darstellung von ${\displaystyle w_{1}}$ beginnt. In der schwachen Linksordnung muss die Darstellung von ${\displaystyle w_{2}}$ mit der einer Darstellung von ${\displaystyle w_{1}}$ enden. In dieser Form sieht man direkt, dass es sich um verschiedene Ordnungen handelt, aber sowohl die schwache Rechts- also auch Linksordnung schwächer sind als die Bruhat-Ordnung. Das heißt wenn ${\displaystyle w_{1}\leq _{R}w_{2}}$ oder ${\displaystyle w_{1}\leq _{L}w_{2}}$ folgt sofort ${\displaystyle w_{1}\leq w_{2}}$. Die Umkehrung gilt jedoch nicht, mit Hilfe der Teilwortcharakterisierung lassen sich schnell Gegenbeispiele finden.

Für die symmetrischen Gruppen ${\displaystyle S_{n}}$ (mit den Transpositionen adjazenter Elemente als Erzeugendensystem) erhält man für ${\displaystyle n=2}$ den vollständigen Graphen ${\displaystyle K_{2}}$, für ${\displaystyle n=3}$ den Kreisgraphen ${\displaystyle C_{6}}$ und für ${\displaystyle n=4}$ den abgeschnittenen Oktaedergraphen.

• James E. Humphreys: Reflection groups and coxeter groups (= Cambridge studies in advanced mathematics. Nr. 29). Cambridge University Press, Cambridge 1990, ISBN 978-0-511-62364-6. 

• Bruhat Graph (MathWorld)