Bruhat-Graph

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.

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.

• Bruhat Graph (MathWorld)