Satz von Dilworth

Der Satz von Dilworth ist ein mathematischer Lehrsatz, welcher sowohl der Ordnungstheorie als auch der Diskreten Mathematik zuzuordnen ist. Er gilt als einer der fundamentalen Sätze der sogenannten Matching theory.[1][2]

Der Satz geht zurück auf eine Arbeit von Robert Palmer Dilworth aus dem Jahr 1950.[3] Er macht eine grundlegende Aussage über das Zusammenspiel zwischen Ketten und Antiketten in einer Halbordnung.

Der Satz in vier Versionen

Sei eine Halbordnung mit endlicher Grundmenge . Dann gilt:

Erste Version

Die größte Mächtigkeit einer Antikette von ist gleich der kleinsten Anzahl von Ketten, die eine disjunkte Zerlegung der Grundmenge bilden.[4]

Zweite Version

Ist     die Spernerzahl von    , so lässt sich die Grundmenge     in     Ketten     disjunkt zerlegen:
.
Umgekehrt:
Ist     die kleinsten Anzahl von Ketten, welche eine disjunkte Zerlegung der Grundmenge     bilden, dann hat     die Spernerzahl     .

Dritte Version

Es gibt eine disjunkte Zerlegung die Grundmenge   in Ketten und dazu ein Repräsentantensystem, welches zugleich eine Antikette von bildet.

Vierte Version

Wenn in keine Antikette der Anzahl   existiert, so lässt sich die Grundmenge stets als Vereinigungsmenge von Ketten darstellen.[5]

Erläuterungen

  1. Eine Kette ist eine Teilmenge , welche sich dadurch auszeichnet, dass ihr alle Elemente in der gegebenen Halbordnungsrelation paarweise vergleichbar sind, d. h. für gilt stets oder .
  2. Dagegen zeichnet sich eine Antikette von dadurch aus, dass in ihr je zwei verschiedene Elemente in der gegebenen Halbordnungsrelation „nicht“ vergleichbar sind, d. h. für mit gilt stets und .
  3. Ketten wie Antiketten haben die Vererbungseigenschaft, d. h. jede Teilmenge einer Kette bzw. Antikette ist ihrerseits eine solche.
  4. Die leere Menge und einelementige Mengen sind immer zugleich Ketten und Antiketten.
  5. Wesentlich für viele Schlussfolgerungen der Ordnungstheorie ist der Umstand, dass eine Kette und eine Antikette sich niemals in mehr als einem Element schneiden, dass also die Schnittmenge einer Kette mit einer Antikette stets entweder die leere Menge oder eine einelementige Menge ist.
  6. Die Grundmenge ist die Vereinigung ihrer einelementigen Teilmengen; d. h. es gilt .[6] Es ist also gesichert, dass stets mindestens eine disjunkte Zerlegung besitzt, welche aus lauter Ketten von besteht. Wegen der Endlichkeitsvoraussetzung ist damit weiter gesichert, dass auch immer eine aus lauter solchen Ketten bestehende disjunkte Zerlegung von kleinster Anzahl besitzt. Diese Zahl nennen manche Autoren auch die „Dilworthzahl“ von . Der Satz von Dilworth besagt also, dass „für endliche Halbordnungen Spernerzahl und Dilworthzahl identisch sind“.[7]

Zum Beweis

Zu dem Satz gibt es eine Reihe von Beweisen. In der neueren Fachliteratur wird oft auf den Beweis von Fred Galvin zurückgegriffen, welcher sich durch besondere Kürze auszeichnet. Ebenfalls häufig findet man in der Fachliteratur den Beweis von Helge Tverberg, welcher die Struktur von Halbordnungen besonders einsichtig macht und dabei ebenfalls kurz ist. Tverbergs Beweis greift auf die Beweisidee von Micha Perles zurück und verfeinert diese noch. Dieser Beweis wird Folgenden skizziert.

Beweisskizze nach Perles und Tverberg

Bewiesen wird der Satz von Dilworth in seiner vierten Version per vollständiger Induktion nach der Anzahl der Elemente von :[8]

Im Falle ist nichts weiter zu zeigen, da die leere Menge stets als Vereinigungsmenge von beliebig vielen Kopien ihrer selbst darstellbar ist.

Nun gelte als Induktionsvoraussetzung, dass und dass der Satz schon für alle endlichen Halbordnungen einer Anzahl gültig sei.

Dann lässt sich zunächst schließen, dass sein muss. Denn anderenfalls ergäbe sich aus der Voraussetzung, dass keine Elemente enthielte und damit wäre, was der Induktionsvoraussetzung widerspräche.

Weiterhin existiert aus Endlichkeitsgründen in eine maximale Kette, also eine Kette , welche in keine andere Kette als echte Obermenge hat.[9]

Das größte Element von [10] werde mit , das kleinste mit bezeichnet. Offenbar ist ein maximales Element und ein minimales Element von . Denn andernfalls ließe sich die Kette um ein Element erweitern, hätte also eine andere Kette als Obermenge – im Widerspruch zu ihrer Maximalität.

Für werden nun zwei Fälle unterschieden:

Fall 1
In existiert keine Antikette mit Elementen.

Dann ist wegen und der Induktionsvoraussetzung Vereinigungsmenge von Ketten und folglich als Vereinigungsmenge von Ketten darstellbar.

Fall 2
In existiert eine Antikette mit genau Elementen .

Diese Antikette hat die Eigenschaft, dass jedes Element von mit mindestens einem ihrer Elemente vergleichbar ist. Denn andernfalls entstünde ein Widerspruch zu der Voraussetzung, dass keine Antikette mit Elementen enthält.

Folglich lässt sich in der Form

darstellen mit

  .[11]

ist dabei sowohl gleich der Menge der maximalen Elemente von als auch gleich der Menge der minimalen Elemente von , wobei offenbar

ist.

Also folgt weiter und gleichzeitig . Daher ist sowohl als auch .

Nach Induktionsvoraussetzung lassen sich folglich Ketten und finden, welche die Gleichungen

und

erfüllen. Deren Indizierung kann dabei so gewählt werden, dass für jedes   zugleich das größte Element von und das kleinste Element von ist.

Fügt man für alle jeweils und mittels Vereinigung zusammen, so entstehen neue Ketten

von .

Mit diesen ergibt sich nun insgesamt

und damit die Schlussfolgerung, dass als Vereinigungsmenge von Ketten darstellbar ist.

Dies vollendet den Induktionsschritt und den Beweis.

Verwandte Sätze

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 in dem Sinne, dass sich jeder dieser Sätze leicht aus jedem der anderen herleiten lässt.[12]

Der Satz von Birkhoff-von Neumann ist eine direkte Folgerung aus dem Satz von Hall und wird damit auch durch den Satz von Dilworth impliziert.[13]

Von den beiden Mathematikern Gallai und Milgram liegt ein 1960 veröffentlichter, graphentheoretischer Satz vor, der dem Satz von Dilworth ähnlich und sogar etwas allgemeiner ist.[14][15]

Herleitung des Heiratssatzes aus dem Satz von Dilworth

Die engen Beziehungen zwischen der fünf genannten Sätzen (Sätze von Dilworth, Hall, König und Menger sowie das Max-Flow-Min-Cut-Theorem) werden deutlich anhand der Herleitungen, mit denen gezeigt wird, dass jeder einzelne jeden anderen nach sich zieht. Ein Beispiel hierfür gibt die Herleitung des Heiratssatzes aus dem Satz von Dilworth, die wie folgt dargestellt werden kann:[16]

Gegeben seien eine endliche Indexmenge und dazu eine Familie endlicher Mengen, welche der Hall-Bedingung

(H)   

genüge. Es darf oBdA dabei angenommen werden, dass die Vereinigungsmenge

und die Indexmenge disjunkt sind.

Dazu wird die Menge mittels

definiert und auf dieser die folgende Halbordnungsrelation  :

Für gelte dann und nur dann, wenn
oder und und .

Dass die Halbordnungseigenschaften besitzt, ist offensichtlich und ebenso, dass eine Antikette von ist. Von grundlegender Bedeutung ist dabei, dass wegen der Hall-Bedingung in keine Antikette mit mehr Elementen als existiert. Dies zeigt die folgende Überlegung:

Angenommen es gibt eine Antikette mit . Für diese ist die außerhalb von liegende Teilmenge gleich . Die Antiketteneigenschaft von bedeutet, dass für ein Element und für ein niemals die Beziehung bestehen kann.

Damit ergibt sich

und zusammen mit (H) weiter

und auf diesem Wege ein Widerspruch.

Das bedeutet: hat die Spernerzahl .

Nach dem Satz von Dilworth besitzt daher eine disjunkte Zerlegung

in Ketten von .

Aufgrund der Definition von bestehen hier alle aus höchstens zwei Elementen. D. h.: lässt sich aufteilen in die Menge derjenigen Elemente von mit und in die Menge derjenigen Elemente von mit .

Nun ist zu berücksichtigen, dass jeder Index von genau einer dieser Ketten erfasst wird. Dies bedeutet, dass die Teilmenge in einer bijektiven Zuordnung zu der Indexmenge steht, bei der zu jedem Element umkehrbar eindeutig ein Index mit

gehört.

Die Bijektion liefert nun die gewünschte injektive Auswahlfunktion. Man nimmt nämlich die Umkehrabbildung , welche offenbar für stets die Beziehung

erfüllt.

Die so gegebene Familie ist damit ein vollständiges System von paarweise verschiedenen Repräsentanten für die Mengenfamilie .

Damit ist insgesamt gezeigt, dass der Satz von Dilworth den Heiratssatz nach sich zieht.

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 auch unendlich sein kann, wobei jedoch die Spernerzahl immer noch eine natürliche Zahl ist. Der Beweis dieser transfiniten Version setzt allerdings üblicherweise als entscheidendes Hilfsmittel das Lemma von Zorn ein, setzt also die Gültigkeit des Auswahlaxioms voraus.[17]

Korollar: Ein Satz von Erdős und Szekeres

Der Satz von Dilworth zieht unmittelbar einen anderen bekannten Satz der Diskreten Mathematik nach sich, welcher auf eine Arbeit von Paul Erdős und George Szekeres aus dem Jahre 1935 zurückgeht. Dieser Satz gilt als eines der ersten Resultate der sogenannten extremalen Kombinatorik (engl. extremal combinatorics).[18]

Der „Satz von Erdős und Szekeres“ besagt Folgendes:[18]

Seien     und dabei     und sei weiter     eine endliche Folge von     verschiedenen reellen Zahlen in beliebiger Anordnung.
Dann enthält    
eine Teilfolge     mit    
oder
eine Teilfolge     mit     .

Die Herleitung aus dem Satz von Dilworth ergibt sich,[19] indem man die Menge     mit folgender Halbordnungsrelation versieht:

Aus dem Satz von Dilworth folgt nämlich unter den genannten Bedingungen zwingend, dass     mindestens eine Kette der Anzahl     oder aber eine Antikette   der Anzahl     umfasst, womit sich dann auch alles Weitere ergibt.

Dieser Satz von Erdős und Szekeres schließt an einen anderen Satz an, welcher mit dem (in der englischen Literatur) sogenannten Happy Ending problem verbunden ist und der ebenfalls von Erdős und Szekeres in derselben Arbeit 1935 formuliert wurde. Dieser lässt sich formulieren wie folgt:[20]

Zu jeder beliebig vorgegebenen Anzahl         findet man in der euklidischen Ebene innerhalb einer hinreichend großen Menge von endlich vielen Punkten in allgemeiner Lage stets ein konvexes m-Eck.

Literatur

Originalartikel

Monographien

  • Egbert Harzheim: Ordered Sets (= Advances in Mathematics. Band 7). Springer Verlag, New York, NY 2005, ISBN 0-387-24219-8 (MR2127991).
  • Konrad Jacobs: Einführung in die Kombinatorik (= de Gruyter Lehrbuch). de Gruyter, Berlin (u. a.) 1983, ISBN 3-11-008736-7 (MR0720054).
  • L. Lovász und M. D. Plummer: Matching Theory (= North-Holland Mathematics Studies. Band 121). North-Holland, Amsterdam (u. a.) 1986, ISBN 0-444-87916-1 (MR0859549).
  • Leonid Mirsky: Transversal Theory (= North-Holland Mathematics Studies. Band 121). Academic Press, New York / London 1971, ISBN 0-12-498550-5 (MR0282853).
  • Dieter Jungnickel: Transversaltheorie (= Mathematik und ihre Anwendungen in Physik und Technik. Band 39). Akademische Verlagsgesellschaft Geest & Portig K.-G., Leipzig 1982 (MR0706076).
  • Stasys Jukna: Extremal Combinatorics (= Texts in Theoretical Computer Science). Springer Verlag, Heidelberg (u. a.) 2011, ISBN 978-3-642-17363-9 (MR2865719).
  • Konrad Jacobs (Hrsg.): Selecta Mathematica I (= Heidelberger Taschenbücher. Band 49). Springer-Verlag, Berlin / Heidelberg / New York 1969, S. 103–141.
  • Philip F. Reichmeider: The Equivalence of Some Combinatorial Matching Theorems. Polygonal Publishing House, Washington, NJ 1984, ISBN 0-936428-09-0 (MR0781348).
  • Reinhard Diestel: Graph Theory. Springer, New York (u. a.) 1997, ISBN 0-387-98211-6.
  • Joseph P. S. Kung, Gian-Carlo Rota, Catherine H. Yan: Combinatorics: The Rota Way (= Cambridge Mathematical Library). Cambridge University Press, Cambridge (u. a) 2009, ISBN 978-0-521-73794-4 (MR2483561).

Weblinks

Einzelnachweise und Fußnoten

  1. Kung-Rota-Yan: S. 126.
  2. Der Matching theory gehört – neben anderen wichtigen Sätzen – vor allem auch der berühmte Heiratssatz von Philip Hall an.
  3. Dilworth: Annals of Mathematics. Band 51, S. 161 ff.
  4. Für endliche Mengen haben Anzahl und Mächtigkeit dieselbe Bedeutung.
  5. In dieser vierten Version ist nicht ausgeschlossen, dass die Ketten und Antiketten sowie die Grundmenge gleich der leeren Menge sind.
  6. Für ist dies die leere Vereinigungsmenge.
  7. Für unendliche Halbordnungen ist die Situation anders. Hier gilt im Allgemeinen nur, dass die Mächtigkeit einer Antikette niemals die Mächtigkeit einer Kettenzerlegung übersteigen kann; vgl. Harzheim: S. 60–61.
  8. Im Folgenden wird stets statt geschrieben und in entsprechender Weise für alle Teilmengen von . Die Halbordnungsrelation wird also in und allen Teilmengen als fest vorgegeben angenommen.
  9. Beispielsweise kann man dafür in eine längste Kette auswählen, also eine, welche unter allen Ketten von von größter Anzahl ist. Eine solche existiert, denn jede Kette kann offenbar aus höchstens Elementen bestehen. Dabei ist unerheblich, wie man diese Kette findet. Die Endlichkeitsvoraussetzung allein stellt sicher, dass es eine solche gibt.
  10. Bzgl. der Halbordnungsrelation   !
  11. Wie stets ist gleichbedeutend mit .
  12. Zu diesem Zusammenhang gibt es ausführliche Darstellungen bei Jungnickel (S. 90–92), bei Jacobs (S. 38–42) und in dem Beitrag von Jacobs in den Selecta Mathematica I (S. 131–137).
  13. Lovász-Plummer: S. 35–36.
  14. Gallai-Milgram: Acta Sci. Math. (Szeged). S. 183.
  15. Diestel: S. 38–40.
  16. Die hiesige Darstellung folgt der in Selecta Mathematica I. S. 133.
  17. Harzheim: S. 58–60.
  18. a b Jukna: S. 55.
  19. Jukna: S. 71.
  20. Jukna: S. 69.