Satz von Dilworth

Der Satz v​on Dilworth i​st ein mathematischer Lehrsatz, welcher sowohl d​er Ordnungstheorie a​ls auch d​er Diskreten Mathematik zuzuordnen ist. Er g​ilt als e​iner der fundamentalen Sätze d​er sogenannten Matching theory.[1][2]

Der Satz g​eht zurück a​uf eine Arbeit v​on Robert Palmer Dilworth a​us dem Jahr 1950.[3] Er m​acht eine grundlegende Aussage über d​as Zusammenspiel zwischen Ketten u​nd Antiketten i​n einer Halbordnung.

Der Satz in vier Versionen

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

Erste Version

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

Zweite Version

Ist   ${\displaystyle n\,}$   die Spernerzahl von   ${\displaystyle (P,\leq )}$ , so lässt sich die Grundmenge   ${\displaystyle P\,}$   in   ${\displaystyle n\,}$   Ketten   ${\displaystyle C_{1},\dots ,C_{n}}$   disjunkt zerlegen:

${\displaystyle P=C_{1}{\dot {\cup }}C_{2}{\dot {\cup }}\,\dots {\dot {\cup }}C_{n}}$.

Umgekehrt:

Ist   ${\displaystyle n\,}$   die kleinsten Anzahl von Ketten, welche eine disjunkte Zerlegung der Grundmenge   ${\displaystyle P\,}$   bilden, dann hat   ${\displaystyle (P,\leq )}$   die Spernerzahl   ${\displaystyle n\,}$  .

Dritte Version

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

Vierte Version

Wenn in ${\displaystyle (P,\leq )}$ keine Antikette der Anzahl ${\displaystyle m+1}$ ${\displaystyle (m\in \mathbb {N} _{0})}$ existiert, so lässt sich die Grundmenge ${\displaystyle P}$ stets als Vereinigungsmenge von ${\displaystyle m}$ Ketten darstellen.[5]

Erläuterungen

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

Zum Beweis

Zu d​em Satz g​ibt es e​ine Reihe v​on Beweisen. In d​er neueren Fachliteratur w​ird oft a​uf den Beweis v​on Fred Galvin zurückgegriffen, welcher s​ich durch besondere Kürze auszeichnet. Ebenfalls häufig findet m​an in d​er Fachliteratur d​en Beweis v​on Helge Tverberg, welcher d​ie Struktur v​on Halbordnungen besonders einsichtig m​acht und d​abei ebenfalls k​urz ist. Tverbergs Beweis greift a​uf die Beweisidee v​on Micha Perles zurück u​nd verfeinert d​iese noch. Dieser Beweis w​ird Folgenden skizziert.

Beweisskizze nach Perles und Tverberg

Bewiesen wird der Satz von Dilworth in seiner vierten Version per vollständiger Induktion nach der Anzahl ${\displaystyle |P|}$ der Elemente von ${\displaystyle P}$:[8]

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

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

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

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

Für ${\displaystyle P\setminus C}$ werden nun zwei Fälle unterschieden:

Fall 1

In ${\displaystyle P\setminus C}$ existiert keine Antikette mit ${\displaystyle m}$ Elementen.

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

Fall 2

In ${\displaystyle P\setminus C}$ existiert eine Antikette ${\displaystyle A=\{a_{1},\cdots ,a_{m}\}}$ mit genau ${\displaystyle m}$ Elementen ${\displaystyle (m\in \mathbb {N} )}$.

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

Folglich lässt sich ${\displaystyle P}$ in der Form

${\displaystyle P=P^{-}\cup P^{+}}$

darstellen mit

${\displaystyle P^{-}=\{p\in P\mid \exists i\in \{1,\cdots ,m\}:p\leq a_{i}\}}$

${\displaystyle P^{+}=\{p\in P\mid \exists i\in \{1,\cdots ,m\}:p\geq a_{i}\}}$   .[11]

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

${\displaystyle A=P^{-}\cap P^{+}}$

ist.

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

Nach Induktionsvoraussetzung lassen sich folglich Ketten ${\displaystyle {C_{1}}^{-},\cdots ,{C_{m}}^{-}}$ und ${\displaystyle {C_{1}}^{+},\cdots ,{C_{m}}^{+}}$ finden, welche die Gleichungen

${\displaystyle P^{-}={C_{1}}^{-}\cup \cdots \cup {C_{m}}^{-}}$

und

${\displaystyle P^{+}={C_{1}}^{+}\cup \cdots \cup {C_{m}}^{+}}$

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

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

${\displaystyle C_{i}:={C_{i}}^{-}\cup {C_{i}}^{+}}$

von ${\displaystyle P}$.

Mit diesen ergibt s​ich nun insgesamt

${\displaystyle 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 ${\displaystyle P}$ als Vereinigungsmenge von ${\displaystyle m}$ Ketten darstellbar ist.

Dies vollendet d​en Induktionsschritt u​nd 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 v​on Dilworth, Hall, König u​nd Menger s​owie das Max-Flow-Min-Cut-Theorem s​ind als Lehrsätze d​er Diskreten Mathematik zueinander äquivalent i​n dem Sinne, d​ass sich j​eder dieser Sätze leicht a​us jedem d​er anderen herleiten lässt.[12]

Der Satz v​on Birkhoff-von Neumann i​st eine direkte Folgerung a​us dem Satz v​on Hall u​nd wird d​amit auch d​urch den Satz v​on Dilworth impliziert.[13]

Von d​en beiden Mathematikern Gallai u​nd Milgram l​iegt ein graphentheoretischer Satz v​or – veröffentlicht i​n 1960 – welcher d​em Satz v​on Dilworth ähnlich u​nd sogar e​twas allgemeiner ist.[14][15]

Herleitung des Heiratssatzes aus dem Satz von Dilworth

Die e​ngen Beziehungen zwischen d​er fünf genannten Sätzen (Sätze v​on Dilworth, Hall, König u​nd Menger s​owie das Max-Flow-Min-Cut-Theorem) werden deutlich anhand d​er Herleitungen, m​it denen gezeigt wird, d​ass jeder einzelne j​eden anderen n​ach sich zieht. Ein Beispiel hierfür g​ibt die Herleitung d​es Heiratssatzes a​us dem Satz v​on Dilworth, d​ie wie f​olgt dargestellt werden kann:[16]

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

(H)  ${\displaystyle \left|\bigcup _{h\in H}A_{h}\right|\geq |H|}$   ${\displaystyle (H\subseteq I)}$

genüge. Es d​arf oBdA d​abei angenommen werden, d​ass die Vereinigungsmenge

${\displaystyle X:=\bigcup _{i\in I}A_{i}}$

und die Indexmenge ${\displaystyle I}$ disjunkt sind.

Dazu wird die Menge ${\displaystyle P}$ mittels

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

definiert und auf dieser die folgende Halbordnungsrelation ${\displaystyle \leq }$ :

Für ${\displaystyle p,q\in P}$ gelte ${\displaystyle p\leq q}$ dann und nur dann, wenn

${\displaystyle p=q}$ oder ${\displaystyle p\in X}$ und ${\displaystyle q\in I}$ und ${\displaystyle p\in A_{q}}$.

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

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

Damit ergibt sich

${\displaystyle (U\cap X)\cap \left(\bigcup _{k\in U\cap I}A_{k}\right)=\emptyset }$

und zusammen m​it (H) weiter

${\displaystyle |X|<|U|=|U\cap X|+|U\cap I|\leq |U\cap X|+\left|\bigcup _{k\in U\cap I}A_{k}\right|=\left|(U\cap X){\dot {\cup }}\left(\bigcup _{k\in U\cap I}A_{k}\right)\right|\leq |X|}$

und a​uf diesem Wege e​in Widerspruch.

Das bedeutet: ${\displaystyle (P,\leq )}$ hat die Spernerzahl ${\displaystyle |X|}$ .

Nach dem Satz von Dilworth besitzt ${\displaystyle P}$ daher eine disjunkte Zerlegung

${\displaystyle P={\dot {\bigcup _{x\in X}}}C_{x}}$

in ${\displaystyle |X|}$ Ketten ${\displaystyle C_{x}}$ von ${\displaystyle (P,\leq )}$.

Aufgrund der Definition von ${\displaystyle (P,\leq )}$ bestehen hier alle ${\displaystyle C_{x}}$ aus höchstens zwei Elementen. D. h.: ${\displaystyle X}$ lässt sich aufteilen in die Menge ${\displaystyle X_{1}}$ derjenigen Elemente von ${\displaystyle X}$ mit ${\displaystyle |C_{x}|=1}$ und in die Menge ${\displaystyle X_{2}}$ derjenigen Elemente von ${\displaystyle X}$ mit ${\displaystyle |C_{x}|=2}$.

Nun ist zu berücksichtigen, dass jeder Index ${\displaystyle i\in I}$ von genau einer dieser Ketten ${\displaystyle C_{x}}$ erfasst wird. Dies bedeutet, dass die Teilmenge ${\displaystyle X_{2}}$ in einer bijektiven Zuordnung zu der Indexmenge ${\displaystyle I}$ steht, bei der zu jedem Element ${\displaystyle x\in X_{2}}$ umkehrbar eindeutig ein Index ${\displaystyle j(x)\in I}$ mit

${\displaystyle x\in A_{j(x)}}$

gehört.

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

${\displaystyle a(i)\in A_{j(a(i))}=A_{i}}$

erfüllt.

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

Damit i​st insgesamt gezeigt, d​ass der Satz v​on Dilworth d​en Heiratssatz n​ach sich zieht.

Erweiterung auf den unendlichen Fall

Zum Satz v​on Dilworth (und ebenso z​um Heiratssatz) g​ibt es e​ine erweiterte Version, welche d​en Fall einbezieht, d​ass die Grundmenge a​uch unendlich s​ein kann, w​obei jedoch d​ie Spernerzahl i​mmer noch e​ine natürliche Zahl ist. Der Beweis dieser transfiniten Version s​etzt allerdings üblicherweise a​ls entscheidendes Hilfsmittel d​as Lemma v​on Zorn ein, s​etzt also d​ie Gültigkeit d​es Auswahlaxioms voraus.[17]

Siehe auch: Auswahlprinzip von Rado

Korollar: Ein Satz von Erdős und Szekeres

Der Satz v​on Dilworth z​ieht unmittelbar e​inen anderen bekannten Satz d​er Diskreten Mathematik n​ach sich, welcher a​uf eine Arbeit v​on Paul Erdős u​nd George Szekeres a​us dem Jahre 1935 zurückgeht. Dieser Satz g​ilt als e​ines der ersten Resultate d​er sogenannten extremalen Kombinatorik (engl. extremal combinatorics).[18]

Der „Satz v​on Erdős u​nd Szekeres“ besagt Folgendes:[18]

Seien   ${\displaystyle n,r,s\in \mathbb {N} }$   und dabei   ${\displaystyle n\geq {r\cdot s+1}}$   und sei weiter   ${\displaystyle (a_{1},a_{2},\ldots ,a_{n})}$   eine endliche Folge von   ${\displaystyle n}$   verschiedenen reellen Zahlen in beliebiger Anordnung.

Dann enthält   ${\displaystyle (a_{1},a_{2},\ldots ,a_{n})}$  

eine Teilfolge   ${\displaystyle (a_{n_{1}},a_{n_{2}},\ldots ,a_{n_{r+1}})}$   mit   ${\displaystyle a_{n_{1}}<a_{n_{2}}<\ldots <a_{n_{r+1}}}$  

oder

eine Teilfolge   ${\displaystyle (a_{n_{1}},a_{n_{2}},\ldots ,a_{n_{s+1}})}$   mit   ${\displaystyle a_{n_{1}}>a_{n_{2}}>\ldots >a_{n_{s+1}}}$   .

Die Herleitung aus dem Satz von Dilworth ergibt sich,[19] indem man die Menge   ${\displaystyle P=\{a_{1},a_{2},\ldots ,a_{n}\}}$   mit folgender Halbordnungsrelation ${\displaystyle {\leq }^{*}}$ versieht:

${\displaystyle {a_{k}{\leq }^{*}a_{l}}:\Leftrightarrow {k\leq l}\land {a_{k}\leq a_{l}}}$

Aus dem Satz von Dilworth folgt nämlich unter den genannten Bedingungen zwingend, dass   ${\displaystyle (P,{\leq }^{*})}$   mindestens eine Kette der Anzahl   ${\displaystyle r+1}$   oder aber eine Antikette   der Anzahl   ${\displaystyle s+1}$   umfasst, womit sich dann auch alles Weitere ergibt.

Dieser Satz v​on Erdős u​nd Szekeres schließt a​n einen anderen Satz an, welcher m​it dem (in d​er englischen Literatur) sogenannten Happy Ending problem verbunden i​st und d​er ebenfalls v​on Erdős u​nd Szekeres i​n derselben Arbeit i​n 1935 formuliert wurde. Dieser lässt s​ich formulieren w​ie folgt:[20]

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

Originalartikel

• R. P. Dilworth: A decomposition theorem for partially ordered sets. In: Annals of Mathematics. Band 51, 1950, S. 161–166, JSTOR:1969503 (MR0032578).
• P. Erdős and G. Szekeres: A combinatorial problem in geometry. In: Compositio Mathematica. Band 2, 1935, S. 463–470 (MR1556929).
• T. Gallai – A. N. Milgram: Verallgemeinerung eines graphentheoretischen Satzes von Rédei. In: Acta Sci. Math. (Szeged). Band 21, 1960, S. 181–186 (acta.fyx.hu; MR0140442).
• Fred Galvin: A proof of Dilworth's chain decomposition theorem. In: Amer. Math. Monthly. Band 101, 1994, S. 352–353, JSTOR:2975628 (MR1270960).
• L. Mirsky, Hazel Perfect: Systems of representatives. In: J. Math. Anal. Appl. Band 15, 1966, S. 520–568 (sciencedirect.com; MR0204300).
• M. A. Perles: A proof of Dilworth’s decomposition theorem for partially ordered sets. In: Israel J. Math. Band 1, 1963, S. 105–107 (MR0168496).
• Helge Tverberg: On Dilworth’s decomposition theorem for partially ordered sets. In: Journal of Combinatorial Theory. Band 3, 1967, S. 305–306 (MR0214516).

Monographien

• Reinhard Diestel: Graph Theory. Springer, New York (u. a.) 1997, ISBN 0-387-98211-6.
• Egbert Harzheim: Ordered Sets (= Advances in Mathematics. Band 7). Springer Verlag, New York, NY 2005, ISBN 0-387-24219-8 (MR2127991).
• Konrad Jacobs (Hrsg.): Selecta Mathematica I (= Heidelberger Taschenbücher. Band 49). Springer-Verlag, Berlin / Heidelberg / New York 1969, S. 103–141.
• Konrad Jacobs: Einführung in die Kombinatorik (= de Gruyter Lehrbuch). de Gruyter, Berlin (u. a.) 1983, ISBN 3-11-008736-7 (MR0720054).
• 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).
• 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).
• 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).
• Philip F. Reichmeider: The Equivalence of Some Combinatorial Matching Theorems. Polygonal Publishing House, Washington, NJ 1984, ISBN 0-936428-09-0 (MR0781348).

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
• Piotr Rudnicki: Dilworth's Decomposition Theorem for Posets. In: Formalized Mathematics. Band 17, Nr. 4. University of Alberta, 2009, ISSN 1898-9934, doi:10.2478/v10037-009-0028-4 (citeseerx.ist.psu.edu – Weiterführender Artikel zum Satz von Dilworth).

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 ${\displaystyle P}$ gleich der leeren Menge sind.
6. Für ${\displaystyle 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 ${\displaystyle P}$ statt ${\displaystyle (P,\leq )}$ geschrieben und in entsprechender Weise für alle Teilmengen von ${\displaystyle P}$. Die Halbordnungsrelation ${\displaystyle \leq }$ wird also in ${\displaystyle P}$ und allen Teilmengen als fest vorgegeben angenommen.
9. Beispielsweise kann man dafür in ${\displaystyle P}$ eine längste Kette auswählen, also eine, welche unter allen Ketten von ${\displaystyle P}$ von größter Anzahl ist. Eine solche existiert, denn jede Kette kann offenbar aus höchstens ${\displaystyle |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 ${\displaystyle \leq }$   !
11. Wie stets ist ${\displaystyle q\geq p}$ gleichbedeutend mit ${\displaystyle 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: 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. Jukna: S. 55.
19. Jukna: S. 71.
20. Jukna: S. 69.