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=⟨r1,…,rn∣(rirj)mij=1⟩ mit Erzeugern S={r1,…,rn}. Für w∈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

w1≤w2⟺ ein Teilstring eines reduzierten Wortes für w2 ist ein reduziertes Wort für w1

definierte Halbordnung.

Der Bruhat-Graph ist der Graph mit Knotenmenge W, in dem es genau dann eine gerichtete Kante von w1 und w2 gibt, wenn w1w2−1 eine „Spiegelung“, d. h. von der Form w1w2−1=wsw−1 mit w∈W,s∈S, und l(w1)<l(w2) ist.

Eigenschaften

Die Ordnung macht (W,≤) zu einer halbgeordneten Menge. Die Relation erfüllt eine Form der Hochhebungseigenschaft: Ist u≤w für zwei Elemente aus W und existiert s∈S mit sw≤w und u≤su so gilt auch su≤w und u≤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 u≤w so existiert eine Kette u=v0≤v1≤⋯≤vn=w mit der Eigenschaft l(vi)=l(u)+i für alle i=1,…,n.

Schwache Ordnung

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

w1≤Rw2⟺∃n∈ℕ,s1,…,sn∈S:w2=w1s1…sn und l(w1s1…si)=l(w1)+i ∀i=1…n

Und analog die schwache Linksordnung:

w1≤Lw2⟺∃n∈ℕ,s1,…,sn∈S:w2=s1…snw1 und l(s1…siw1)=l(w1)+i ∀i=1…n

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

Beispiele

Bruhat_order_S^4
Der Bruhat-Graph von S4

Für die symmetrischen Gruppen Sn (mit den Transpositionen adjazenter Elemente als Erzeugendensystem) erhält man für n=2 den vollständigen Graphen K2, für n=3 den Kreisgraphen C6 und für n=4 den abgeschnittenen Oktaedergraphen.