Logo

DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000

Der Satz von Dilworth

Satz von Dilworth In jeder endlichen (!) geordneten Menge (M,£) ist die minimale Mächtigkeit einer Partition von M in Ketten gleich der maximalen Mächtigkeit einer Antikette.
Direkter Beweis
Beweis mit dem Satz von König

Es gibt eine interessante Folgerung: Nehmen Sie entweder diese Folge von 37 Zufallszahlen, oder verändern Sie sie. Drücken Sie "Auf" bzw "Ab", so sucht der Computer alle schwach aufsteigenden bzw absteigenden Teilfolgen der Länge 6. Dabei ist a0, a1, a2, a3, a4, a5, a6 schwach aufsteigend, falls a0 £ a1 £ a2 £ a3 £ a4 £ a5 £ a6 gilt.



Ergebnis:
Offenbar findet der Computer immer eine schwach aufsteigende oder eine schwach absteigende 6-er Teilfolge. Warum? Darum:
Satz von Erdös/Szekeres 1935 In jeder endlichen Folge von n2+1 natürlicher Zahlen gibt es eine schwach aufsteigende Teilfolge der Länge n+1 oder eine schwach absteigende Teilfolge der Länge n+1.
Beweis: Die Folge sei (ai)0£i £m mit m = n2. Wir ordnen die Menge {0,1, ... , n2} durch i R j falls (i £ j) und (ai £ aj). Antiketten in R entsprechen den schwach absteigenden Teilfolge, und Ketten in R entsprechen den schwach aufsteigenden Teilfolge. (Denn sei etwa {i,j,k} eine Antikette, mit etwa i < j < k. Dann ist ai > aj und aj > ak. Ist {i,j,k} Kette, so ist ai £ aj und aj £ ak) Wenn wir also keine schwach absteigende Teilfolge mit n+1 Elementen haben, dann ist die maximale Mächtigkeit einer Antikette in ({0,1,...,n2},R) höchstens n. Nach obigem Satz von Dilworth gibt es eine Überdeckung aller Elemente von R durch höchstens n Ketten---wären alle Kettenlängen kleiner als n+1, so wäre das (nach dem Taubenschlagprinzip) unmöglich.

Übungsaufgabe: In jeder endlichen geordneten Menge (M,£) ist die minimale Mächtigkeit einer Partition von M in Antiketten gleich der maximalen Mächtigkeit einer Kette. (Trotz Ähnlichkeit ist dies viel leichter zu beweisen als der Satz von Dilworth)

Reduktion auf Matchings in bipartiten Graphen

Zum Schluß zeigen wir, wie sich das Problem, Partitionen in die kleinstmögliche Zahl von Ketten zu finden, auf ein Matchingproblem in einem bipartiten Graphen zurückführen läßt. Zu einer endlichen geordneten Menge (X,£) definieren wir einen bipartiten Graphen mit zwei disjunkt gemachten Kopien von X als Eckenmenge: A = {x°/x Î X}, B = {x*/x Î X}. x° und y* sind genau dann benachbart, falls x £ y aber x ¹ y ist. Anschaulich setzen wir alle "transitiven Linien" ins Hasse-Diagramm ein, und schneiden jeden Punkt x in zwei Teile. Die oberen Hälften x°, zusammen mit den anstossenden Linien, kommen an den unteren Bildrand, die unteren Hälften x* an den oberen Bildrand, siehe das Beispiel.
Da bei einer Partition in Ketten jeder Punkt höchstens einmal eine Kettenverbindung nach oben und höchstens einmal eine Kettenverbindung nach unten hat, wird aus so einer Kettenpartition ein Matching im bipartiten Graphen (beachten sie, daß diese Kettenverbindungen, wie in Beispiel 2, nicht immer Hasse-Linien sind). Umgekehrt setzen sich Matchings im bipartiten Graphen zu Ketten in der geordneten Menge zusammen. Nicht jedes Element liegt dann in einer Kette, aber wir fügen einfach einelementige Ketten hinzu, bis das erreicht ist.
Bei einer Kettenpartition der n Elemente von X mit k Ketten, haben wir dann n-k Kettenlinien, also n-k Kanten im Matching im bipartiten Graphen, und umgekehrt. D.h. die kleinste Zahl von Ketten, die (X,£) partitioniert, plus der Mächtigkeit eines größten Matchings des zugeordneten bipartiten Graphen ist gleich |X|.

Damit ist auch obiger Satz von Dilworth schnell bewiesen: Sei wieder k die kleinste Zahl von Ketten, in die sich die geordnete Menge (X,£) partitionieren läßt. Jedes größte Matching des entsprechenden bipartiten Graphen hat dann |X|-k Elemente, mit dem Satz von König gibt es also eine V-E-Überdeckung mit |X|-k Elementen. Wir betrachten die Teilmenge S von X, bestehend aus den Elementen x Î X für die weder x° noch x* in dieser V-E-Überdeckung liegen. Natürlich ist |S| ³ |X| - (|X|-k) = k. S bildet aber eine Antikette in der geordneten Menge, (überprüfen Sie das!), womit der Beweis erbracht ist.
Erich Prisner
erstellt im Juli 2000.