MiMa-Sortierungen

Ordnungsmatrizen als obere Dreiecksmatrizen

Sei P={p1,,pn}P=\{p_1,\dots ,p_n\} ein endliches Poset. Dann können wir seine Elemente als Vektor (p1,,pn)(p_1,\dots ,p_n) schreiben. Damit werden die Elemente von PP sortiert. Ist so ein Vektor gegeben sprechen wir auch von einer Sortierung. (Mi(p1),,Mi(pn)(|\Mi(p_1)|,\dots ,|\Mi(p_n|) nennen wir den Mi-Vektor der Sortierung und (Ma(p1),,Ma(pn)(|\Ma(p_1)|,\dots ,|\Ma(p_n|) ihren Ma-Vektor.
Gilt für eine Sortierung kl    μ(pk)μ(pl)k\le l \iff \my(p_k)\le \my(p_l), so nennen wir sie Mi-Sortierung. Ihr Vektor bildet eine monoton wachsende endliche Folge von natürlichen Zahlen. Analog nennen wir (p1,,pn)(p_1,\dots ,p_n) Ma-sortiert, falls kl    ν(pk)ν(pl)k\le l \iff -\ny(p_k)\le -\ny(p_l). Der Ma-Vektor ist dementsprechend eine monoton fallende Folge natürlicher Zahlen. Da μ\my und ν\ny nicht injektiv sein muss, ist diese Soritierung nicht eindeutig bestimmt.

Satz

Seien p1,,pnPp_1,\dots ,p_n\in P die Elemente eines endlichen Poset Mi-sortiert oder Ma-sortiert. Dann ist die Ordnungsmatrix eine obere Diagonalmatrix.

Beweis

Zu zeigen ist: für i>ji>j gilt mij=0m_{ij}=0. Angenommen mij=1m_{ij}=1, dann gilt pipjp_i\le p_j, also Mi(pi)Mi(pj)\Mi(p_i)\subseteq \Mi(p_j). Wegen jij\le i und da PP Mi-sortiert ist, gilt: Mi(pj)Mi(pi)|\Mi(p_j)|\le |\Mi(p_i)|. Damit kann Mi(pi)\Mi(p_i) keine echte Teilmenge von Mi(pj)\Mi(p_j) sein und es gilt Mi(pi)=Mi(pj)\Mi(p_i)=\Mi(p_j). Damit gilt pi,pjMi(pi)=Mi(pj)p_i,p_j\in Mi(p_i)=\Mi(p_j), also pipjpip_i\le p_j\le p_i, damit pi=pjp_i=p_j im Widerspruch zu iji\ne j. Für die Ma-Sortierung führt man den Beweis analog. \qed
3-0002.png
Nun stellt sich die Frage, ob eine Mi-Sortierung auch ein Ma-Sortierung ist. Im nebenstehende Hassediagramm ist die Sortierung (a,b,c)(a,b,c) eine Mi-Sortierung mit dem Mi-Vektor (1,1,2)(1,1,2) und auch eine Ma-Sortierung (Ma-Vektor: (2,1,1)(2,1,1)). Tauschen wird die Positionen von aa und bb, bleibt die Mi-Sortierung erhalten, die Ma-Sortierung ist aber nicht mehr gegeben.

Vermutung

Unter allen Mi-Sortierung finden wir wenigstens eine, die gleichzeitig eine Ma-Sortierung ist.

Wir nennen p1,,pnPp_1,\dots ,p_n\in P MiMa-sortiert, falls kl    μ(pk)+ν(pk)μ(pl)+ν(pl)k\le l \iff \my(p_k)+\ny(p_k)\le \my(p_l)+\ny(p_l).

Vermutung

Jede MiMa-Sortierung ist sowohl eine Mi- als auch eine Ma-Sortierung.
 
 

Die ganzen Zahlen hat der liebe Gott geschaffen, alles andere ist Menschenwerk.

Leopold Kronecker

Copyright- und Lizenzinformationen: Diese Seite ist urheberrechtlich geschützt und darf ohne Genehmigung des Autors nicht weiterverwendet werden.
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе