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.)

Definition

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

Die Bruhat-Ordnung ist die auf $W$ durch

$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 $W$, in dem es genau dann eine gerichtete Kante von $w_{1}$ und $w_{2}$ gibt, wenn $w_{1}w_{2}^{-1}$ eine "Spiegelung", d. h. von der Form $w_{1}w_{2}^{-1}=wsw^{-1}$ mit $w\in W,s\in S$, und $l(w_{1})<l(w_{2})$ ist.

Beispiele

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

Weblinks

• Bruhat Graph (MathWorld)