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.

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

Der Satz in vier Versionen

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

Erste Version

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

Zweite Version

Ist   $n$   die Spernerzahl von   $(P,\le )$ , 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,\le )$   die Spernerzahl   $n$  .

Dritte Version

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

Vierte Version

Wenn in $(P,\le )$ keine Antikette der Anzahl $m+1$ $(m\in {\mathbb{N}}_0)$ existiert, so lässt sich die Grundmenge $P$ stets als Vereinigungsmenge von $m$ Ketten darstellen.

Erläuterungen

1. Eine Kette ist eine Teilmenge $C\subseteq (P,\le )$, 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,\le )$ 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\ne b$ gilt stets $a\le ̸b$ und $b\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 $\mathrm{\varnothing }$ 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\}$. Es ist also gesichert, dass $P$ stets mindestens eine disjunkte Zerlegung besitzt, welche aus lauter Ketten von $(P,\le )$ 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,\le )$. Der Satz von Dilworth besagt also, dass „für endliche Halbordnungen Spernerzahl und Dilworthzahl identisch sind“.

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 $|P|$ der Elemente von $P$:

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.

Das größte Element von $C$ 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 \mathbb{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 \mathrm{\exists }i\in \{1,\cdots ,m\}:p\le a_i\}$

$P^{+}=\{p\in P\mid \mathrm{\exists }i\in \{1,\cdots ,m\}:p\ge a_i\}$   .

$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

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

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.

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.

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:

Gegeben seien eine endliche Indexmenge $I$ und dazu eine Familie $𝒜=(A_i{)}_{i\in I}$ endlicher Mengen, welche der Hall-Bedingung

(H)  $\left|\bigcup _{h\in H}{A}_h\right|\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 $\le$ :

Für $p,q\in P$ gelte $p\le q$ dann und nur dann, wenn

$p=q$ oder $p\in X$ und $q\in I$ und $p\in A_q$.

Dass $\le$ die Halbordnungseigenschaften besitzt, ist offensichtlich und ebenso, dass $X$ eine Antikette von $(P,\le )$ ist. Von grundlegender Bedeutung ist dabei, dass wegen der Hall-Bedingung in $(P,\le )$ keine Antikette $U$ mit mehr Elementen als $X$ existiert. Dies zeigt 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 \left(\bigcup _{k\in U\cap I}{A}_k\right)=\mathrm{\varnothing }$

und zusammen mit (H) weiter

$|X|<|U|=|U\cap X|+|U\cap I|\le |U\cap X|+\left|\bigcup _{k\in U\cap I}{A}_k\right|=|(U\cap X)\dot{\cup }\left(\bigcup _{k\in U\cap I}{A}_k\right)|\le |X|$

und auf diesem Wege ein Widerspruch.

Das bedeutet: $(P,\le )$ 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,\le )$.

Aufgrund der Definition von $(P,\le )$ 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 Indexmenge $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:X_2\to I$ liefert nun die gewünschte injektive Auswahlfunktion. Man nimmt nämlich die Umkehrabbildung $a:=j^{-1}: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 $𝒜=(A_i{)}_{i\in I}$.

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. Vorlage:Siehe auch

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

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

Seien   $n,r,s\in \mathbb{N}$   und dabei   $n\ge r\cdot s+1$   und sei weiter   $(a_1,a_2,\dots ,a_n)$   eine endliche Folge von   $n$   verschiedenen reellen Zahlen in beliebiger Anordnung.

Dann enthält   $(a_1,a_2,\dots ,a_n)$  

eine Teilfolge   $(a_{n_1},a_{n_2},\dots ,a_{n_{r+1}})$   mit   $a_{n_1}<a_{n_2}<\dots <a_{n_{r+1}}$  

oder

eine Teilfolge   $(a_{n_1},a_{n_2},\dots ,a_{n_{s+1}})$   mit   $a_{n_1}>a_{n_2}>\dots >a_{n_{s+1}}$   .

Die Herleitung aus dem Satz von Dilworth ergibt sich, indem man die Menge   $P=\{a_1,a_2,\dots ,a_n\}$   mit folgender Halbordnungsrelation ${\le }^{*}$ versieht:

$a_k{\le }^{*}{a}_l:\iff k\le l\wedge a_k\le a_l$

Aus dem Satz von Dilworth folgt nämlich unter den genannten Bedingungen zwingend, dass   $(P,{\le }^{*})$   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 verbunden ist und der ebenfalls von Erdős und Szekeres in derselben Arbeit 1935 formuliert wurde. Dieser lässt sich formulieren wie folgt:

Zu jeder beliebig vorgegebenen Anzahl   $m\in \mathbb{N}$     $(m\ge 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

Originalartikel

• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur

Monographien

• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur

Weblinks

• Kombinatorische Methoden in der Informatik (PDF; 1,4 MB – Skript einer Vorlesung von Peter Hauck, Uni Tübingen, SS 2008)
• Dilworth’s Theorem auf PlanetMath
• Dilworth’s Lemma auf MathWorld
• Vorlage:Literatur