Satz von Dilworth

mathematischer Satz

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

Bearbeiten

Sei   eine Halbordnung mit endlicher Grundmenge  . Dann gilt:

Erste Version

Bearbeiten
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

Bearbeiten
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

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

Vierte Version

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

Erläuterungen

Bearbeiten
  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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

Originalartikel

Monographien

Bearbeiten

Einzelnachweise und Fußnoten

Bearbeiten
  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.