Satz von Dilworth

Der Satz von Dilworth (nach Robert Palmer Dilworth) ist ein mathematischer Lehrsatz, welcher sowohl der Ordnungstheorie als auch der Diskreten Mathematik zuzuordnen ist. Er stellt einen Zusammenhang zwischen Ketten und Antiketten in einer Halbordnung her.

Der Satz

Sei $(P, \leq)$ eine Halbordnung mit endlicher Grundmenge P. Dann gilt:

Die größte Mächtigkeit einer Antikette von $(P, \leq)$ ist gleich der kleinsten Anzahl von Ketten, die eine disjunkte Zerlegung der Grundmenge P bilden.

Das bedeutet:

Ist n die größte Mächtigkeit einer Antikette von $(P, \leq)$ , so lässt sich die Grundmenge P in n Ketten $C_1,\dots,C_n$ disjunkt zerlegen, d.h. $P = C_1\dot{\cup}C_2\dot{\cup}\,\dots\dot{\cup}C_n$.

Umgekehrt ist n die kleinste Anzahl an Ketten die eine disjunkte Zerlegung der Grundmenge P bilden, dann hat auch jede größte Antikette Mächtigkeit n.

Man kann diesen Sachverhalt auch so formulieren:

In jeder endlichen Halbordnung $(P, \leq)$ gibt es eine disjunkte Zerlegung in Ketten und dazu ein Repräsentantensystem, welches zugleich eine Antikette von $(P, \leq)$ bildet.

Eine Kette ist dabei eine Teilmenge $C \subseteq (P, \leq)$, in der alle Elemente in der gegebenen Ordnungsrelation paarweise vergleichbar sind, d.h. für $a,b \in C$ gilt stets $a \le b$ oder $b \le a$. Dagegen ist eine Antikette eine Teilmenge $A \subseteq (P, \leq)$, in der für je zwei verschiedene Elemente stets gilt, dass sie in der gegebenen Ordnungsrelation nicht vergleichbar sind, d.h. für $a,b \in A$ mit $a \neq b$ gilt stets $a \not\le b$ und $b \not\le a$.

Verwandte Sätze

• Satz von Hall (Heiratssatz)
• Satz von König (Graphentheorie)
• Max-Flow-Min-Cut-Theorem
• Satz von Menger
• Satz von Birkhoff & von Neumann

Die Sätze von Dilworth, Hall, König und Menger sowie das Max-Flow-Min-Cut-Theorem sind als Lehrsätze der Diskreten Mathematik zueinander äquivalent. Das heißt: Jeder dieser fünf Sätze impliziert jeden anderen und wird von diesem impliziert, ist also genau dann wahr, wenn der jeweils andere wahr ist. Zu diesen wichtigen und wohlbekannten Zusammenhang gibt es ausführliche Darstellungen in der Literatur (s. u.), insbesondere bei Jungnickel und in dem Beitrag von Jacobs in den Selecta Mathematica I.

Der Satz von Birkhoff & von Neumann ist eine direkte Folgerung aus dem Satz von Hall (siehe Lovász und Plummer) und wird damit auch durch den Satz von Dilworth impliziert.

Von den beiden Mathematikern Gallai und Milgram liegt ein graphentheoretischer Satz vor - 1960 veröffentlicht, siehe Diestel - welcher dem Satz von Dilworth ähnlich und sogar etwas allgemeiner ist.

Erweiterung auf den unendlichen Fall

Zum Satz von Dilworth (und ebenso zum Heiratssatz) gibt es eine erweiterte Version, welche den Fall einbezieht, dass die Grundmenge unendlich ist. Der Beweis dieser erweiterten Version benötigt allerdings als entscheidendes Hilfsmittel das Lemma von Zorn, setzt also die Gültigkeit des Auswahlaxioms voraus. (Für die Einzelheiten: Siehe Literatur.)

Literatur

• Reinhard Diestel: Graph Theory. Springer, New York (u.a.) 1997, ISBN 0-387-98211-6.

• Konrad Jacobs (Hrsg.): Selecta Mathematica I. Springer, Berlin Heidelberg New York 1969.

(Teil 1 der 5-teiligen Reihe; erschienen als Bd. 49 der Heidelberger Taschenbücher)

• Konrad Jacobs: Einführung in die Kombinatorik. de Gruyter, Berlin (u. a.) 1983, ISBN 3-11-008736-7.

• Egbert Harzheim: Ordered Sets. Springer, New York 2005, ISBN 0-387-24219-8.

• Dieter Jungnickel: Transversaltheorie. Akad. Verl.-Ges. Geest & Portig, Leipzig 1982.

• L. Lovász und M. D. Plummer: Matching Theory. North-Holland, Amsterdam (u.a.) 1986, ISBN 0-444-87916-1.
• Leonid Mirsky: Transversal Theory. Academic Press, New York, London 1971, ISBN 0-12-498550-5.

Weblinks

• http://planetmath.org/encyclopedia/DilworthsTheorem.html Dilworths Theorem auf PlanetMath
• http://mathworld.wolfram.com/DilworthsLemma.html Dilworths Lemma auf MathWorld