Satz von Dilworth

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 (P, \leq) eine Halbordnung mit endlicher Grundmenge P\,. Dann gilt:

Erste Version[Bearbeiten]

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.[4]

Zweite Version[Bearbeiten]

Ist   n \,   die Spernerzahl von   (P, \leq)  , so lässt sich die Grundmenge   P\,   in   n \,   Ketten   C_1,\dots,C_n   disjunkt zerlegen:
 P = C_1\dot{\cup}C_2\dot{\cup}\,\dots\dot{\cup}C_n.
Umgekehrt:
Ist   n \,   die kleinsten Anzahl von Ketten, welche eine disjunkte Zerlegung der Grundmenge   P\,   bilden, dann hat   (P, \leq)   die Spernerzahl   n \,  .

Dritte Version[Bearbeiten]

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

Vierte Version[Bearbeiten]

Wenn in (P, \leq) keine Antikette der Anzahl m+1   (m \in \N_0) existiert , so lässt sich die Grundmenge   P\, stets als Vereinigungsmenge von m Ketten darstellen.[5]

Erläuterungen[Bearbeiten]

  1. Eine Kette ist eine Teilmenge  C \subseteq (P, \leq), welche sich dadurch auszeichnet, dass ihr alle Elemente in der gegebenen Halbordnungsrelation paarweise vergleichbar sind, d.h. für a,b \in C gilt stets a \le b oder b \le a.
  2. Dagegen zeichnet sich eine Antikette von  (P, \leq) dadurch aus, dass in ihr je zwei verschiedene Elemente in der gegebenen Halbordnungsrelation 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.
  3. Ketten wie Antiketten haben die Vererbungseigenschaft, d. h. jede Teilmenge einer Kette bzw. Antikette ist ihrerseits eine solche.
  4. Die leere Menge \emptyset 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 P ist die Vereinigung ihrer einelementigen Teilmengen; d. h. es gilt P = \bigcup_{p\in P} \{ p \}.[6] Es ist also gesichert, dass P stets mindestens eine disjunkte Zerlegung besitzt, welche aus lauter Ketten von (P, \leq) besteht. Wegen der Endlichkeitsvoraussetzung ist damit weiter gesichert, dass P auch immer eine aus lauter solchen Ketten bestehende disjunkte Zerlegung von kleinster Anzahl besitzt. Diese Zahl nennen manche Autoren auch die Dilworthzahl von (P, \leq). 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 |P| der Elemente von P:[8]

Im Falle |P|=0 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 |P|> 0 und dass der Satz schon für alle endlichen Halbordnungen einer Anzahl  < |P| gültig sei.

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

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

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

Für P \setminus C werden nun zwei Fälle unterschieden:

Fall 1
In P \setminus C existiert keine Antikette mit m Elementen.

Dann ist wegen m= (m-1)+1 und der Induktionsvoraussetzung P \setminus C Vereinigungsmenge von m-1 Ketten und folglich P = (P \setminus C) \cup C als Vereinigungsmenge von m Ketten darstellbar.

Fall 2
In P \setminus C existiert eine Antikette A = \{a_1, \cdots, a_m \} mit genau m Elementen (m \in \N).

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

Folglich lässt sich P in der Form

P = P^- \cup P^+

darstellen mit

P^- = \{p \in P \mid \exists i \in \{1, \cdots, m\}: p \leq a_i \}
P^+ = \{p \in P \mid \exists i \in \{1, \cdots, m\}: p \geq a_i \}   .[11]

A ist dabei sowohl gleich der Menge der maximalen Elemente von P^- als auch gleich der Menge der minimalen Elemente von P^+, wobei offenbar

A = P^- \cap P^+

ist.

Also folgt weiter c^+ \in P^+ \setminus P^- und gleichzeitig c^- \in P^- \setminus P^+ . Daher ist sowohl | P^-| < |P| als auch | P^+| < |P|.

Nach Induktionsvoraussetzung lassen sich folglich Ketten {C_1}^-,\cdots,{C_m}^- und {C_1}^+,\cdots,{C_m}^+ finden , welche die Gleichungen

P^- = {C_1}^- \cup  \cdots  \cup {C_m}^-

und

P^+ = {C_1}^+ \cup  \cdots  \cup {C_m}^+

erfüllen. Deren Indizierung kann dabei so gewählt werden, dass für jedes i \in \{1, \cdots, m\}   a_i zugleich das größte Element von {C_i}^- und das kleinste Element von {C_i}^+ ist.

Fügt man für alle i \in \{1, \cdots, m\} jeweils {C_i}^- und {C_i}^+ mittels Vereinigung zusammen, so entstehen m neue Ketten

C_i : = {C_i}^- \cup {C_i}^+

von P.

Mit diesen ergibt sich nun insgesamt

P  = P^- \cup P^+ = ({C_1}^- \cup  \cdots  \cup {C_m}^-) \cup ({C_1}^+ \cup  \cdots  \cup {C_m}^+) = C_1 \cup  \cdots  \cup C_m

und damit die Schlussfolgerung, dass P als Vereinigungsmenge von m 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 graphentheoretischer Satz vor – veröffentlicht in 1960 – welcher 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 I und dazu eine Familie \mathcal A = (A_i)_{i \in I} endlicher Mengen , welche der Hall-Bedingung

(H)  |\bigcup_{h \in H} A_h| \ge |H|   (H \subseteq I)

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

X := \bigcup_{i \in I} A_i

und die Indexmenge I disjunkt sind.

Dazu wird die Menge P mittels

P := X  {\dot{\cup}}  I

definiert und auf dieser die folgende Halbordnungsrelation  \leq  :

Für p,q \in P gelte p \leq  q dann und nur dann, wenn
p = q oder p \in X und q \in I und p \in A_q .

Dass \leq die Halbordnungseigenschaften besitzt, ist offensichtlich und ebenso, dass X eine Antikette von (P, \leq) ist. Von grundlegender Bedeutung ist dabei, dass wegen der Hall-Bedingung in (P, \leq) keine Antikette U mit mehr Elementen als X existiert. Dies zeig die folgende Überlegung:


Angenommen es gibt eine Antikette U mit |U| > |X|. Für diese ist die außerhalb von X liegende Teilmenge gleich  U \cap I . Die Antiketteneigenschaft von U bedeutet, dass für ein Element x \in U \cap X und für ein k \in U \cap I niemals die Beziehung x \in A_k bestehen kann.

Damit ergibt sich

(U \cap X )  \cap (\bigcup_{k \in U \cap I} A_k ) =  \emptyset

und zusammen mit (H) weiter

|X| < |U|= |U \cap X| + |U \cap I|  \leq |U \cap X| + |\bigcup_{k \in U \cap I} A_k | = |(A \cap X )  \dot{\cup} (\bigcup_{k \in U \cap I} A_k)|  \leq |X|

und auf diesem Wege ein Widerspruch.


Das bedeutet: (P, \leq) hat die Spernerzahl |X| .

Nach dem Satz von Dilworth besitzt P daher eine disjunkte Zerlegung

 P =  \dot{\bigcup}_{x \in X} C_x

in |X| Ketten C_x von (P, \leq) .

Aufgrund der Definition von (P, \leq) bestehen hier alle C_x aus höchstens zwei Elementen. D. h.: X lässt sich aufteilen in die Menge X_1 derjenigen Elemente von X mit |C_x| =1 und in die Menge X_2 derjenigen Elemente von X mit |C_x| =2.

Nun ist zu berücksichtigen, dass jeder Index i \in I von genau einer dieser Ketten C_x erfasst wird. Dies bedeutet, dass die Teilmenge X_2 in einer bijektiven Zuordnung zu der Indesxmenge I steht, bei der zu jedem Element x \in X_2 umkehrbar eindeutig ein Index j(x) \in I mit

x \in A_{j(x)}

gehört.

Die Bijektion j \colon X_2 \to I liefert nun die gewünschte injektive Auswahlfunktion. Man nimmt nämlich die Umkehrabbildung a := j^{-1} \colon I \to X_2, welche offenbar für i \in I stets die Beziehung

a(i)  \in A_{j(a(i))} = A_i

erfüllt.

Die so gegebene Familie (a(i))_{i \in I} ist damit ein vollständiges System von paarweise verschiedenen Repräsentanten für die Mengenfamilie \mathcal A = (A_i)_{i \in I}.

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][18]

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).[19]

Der Satz von Erdős und Szekeres besagt Folgendes:[20]

Seien    n, r, s \in \N   und dabei    n \geq  {r \cdot s +1}   und sei weiter    (a_1,a_2,\ldots,a_n)    eine endliche Folge von   n   verschiedenen reellen Zahlen in beliebiger Anordnung.
Dann enthält    (a_1,a_2,\ldots,a_n)   
eine Teilfolge    (a_{n_1},a_{n_2},\ldots,a_{n_{r+1}})    mit   a_{n_1} < a_{n_2} < \ldots  < a_{n_{r+1}}   
oder
eine Teilfolge    (a_{n_1},a_{n_2},\ldots,a_{n_{s+1}})    mit   a_{n_1} > a_{n_2} > \ldots  > a_{n_{s+1}}    .


Die Herleitung aus dem Satz von Dilworth ergibt sich,[21] indem man die Menge    P = \{  a_1,a_2,\ldots,a_n \}    mit folgender Halbordnungsrelation  {\leq}^* versieht:

 { a_k  {\leq}^*   a_l }  :  \Leftrightarrow { k \leq l }  \and  { a_k \leq a_l }


Aus dem Satz von Dilworth folgt nämlich unter den genannten Bedingungen zwingend, dass   (P, {\leq}^* )   mindestens eine Kette der Anzahl    r+1    oder aber eine Antikette   der Anzahl    s+1    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[22] verbunden ist und der ebenfalls von Erdős und Szekeres in derselben Arbeit in 1935 formuliert wurde. Dieser lässt sich formulieren wie folgt[23]:

Zu jeder beliebig vorgegeben Anzahl    m \in \N      ( m  \geq 3 )   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[Bearbeiten]

Monographien[Bearbeiten]

Weblinks[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: In: Annals of Mathematics. 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 P gleich der leeren Menge sind.
  6. Für P = \emptyset 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 P statt (P, \leq) geschrieben und in entsprechender Weise für alle Teilmengen von P. Die Halbordnungsrelation  \leq wird also in P und allen Teilmengen als fest vorgegeben angenommen.
  9. Beispielsweise kann man dafür in P eine längste Kette auswählen, also eine, welche unter allen Ketten von P von größter Anzahl ist. Eine solche existiert, denn jede Kette kann offenbar aus höchstens |P| Elementen bestehen. Dabei ist unerheblich, wie man diese Kette findet. Die Endlichkeitsvoraussetzung allein stellt sicher, dass es eine solche gibt.
  10. Bzgl. der Halbordnungsrelation  \leq   !
  11. Wie stets ist q \geq p gleichbedeutend mit p \leq q.
  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: In: 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. Siehe hierzu auch Rado's Auswahlprinzip.
  19.  Jukna: S. 55.
  20.  Jukna: S. 55.
  21.  Jukna: S. 71.
  22. Siehe im englischsprachigen WIKIPEDIA: [1]
  23.  Jukna: S. 69.