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 geht zurück auf eine Arbeit von Robert Palmer Dilworth aus dem Jahr 1950 [1]. Der Satz macht eine fundamentale Aussage über das Zusammenspiel zwischen Ketten und Antiketten in einer Halbordnung .

Der Satz in drei 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.

Zweite Version[Bearbeiten]

Ist   n \,   die Sperner-Zahl 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 Sperner-Zahl   n \,  .

Dritte Version[Bearbeiten]

In jeder endlichen Halbordnung (P, \leq) gibt es eine disjunkte Zerlegung in Ketten und dazu ein Repräsentantensystem, welches zugleich eine Antikette von (P, \leq) bildet.


Eine Kette ist dabei eine Teilmenge  C \subseteq (P, \leq), in der alle Elemente in der gegebenen Ordnungsrelation paarweise vergleichbar sind, d.h. für a,b \in C gilt stets a \le b oder b \le a. Dagegen ist eine Antikette eine Teilmenge  A \subseteq (P, \leq), in der für je zwei verschiedene Elemente stets gilt, dass sie in der gegebenen Ordnungsrelation 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.

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. Das heißt: Jeder dieser fünf Sätze impliziert jeden anderen und wird von diesem impliziert, ist also genau dann wahr, wenn der jeweils andere wahr ist. Zu diesem wichtigen und wohlbekannten Zusammenhang gibt es ausführliche Darstellungen in der Literatur (s. u.), insbesondere bei Jungnickel und in dem Beitrag von Jacobs in den Selecta Mathematica I.

Der Satz von Birkhoff & von Neumann ist eine direkte Folgerung aus dem Satz von Hall (siehe Lovász und Plummer) und wird damit auch durch den Satz von Dilworth impliziert.

Von den beiden Mathematikern Gallai und Milgram liegt ein graphentheoretischer Satz vor - 1960 veröffentlicht, siehe Diestel - welcher dem Satz von Dilworth ähnlich und sogar etwas allgemeiner ist.

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 unendlich ist. Der Beweis dieser transfiniten Version setzt allerdings üblicherweise als entscheidendes Hilfsmittel das Lemma von Zorn ein, geht also vom Auswahlaxioms aus [2].

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

Der Satz von Erdös und Szekeres besagt folgendes[4]:

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[5], 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[6] verbunden ist und der ebenfalls von Erdös und Szekeres in derselben Arbeit in 1935 formuliert wurde. Dieser lässt sich formulieren wie folgt[7]:

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]

  • R. P. Dilworth: A decomposition theorem for partially ordered sets. In: Annals of Mathematics. 51, 1950, S. 161–166.
  • P. Erdős and G. Szekeres: A combinatorial problem in geometry. In: Compositio Mathematica. 2, 1935, S. 463-470.

Monographien[Bearbeiten]

(Teil 1 der 5-teiligen Reihe; erschienen als Bd. 49 der Heidelberger Taschenbücher)
  •  Konrad Jacobs: Einführung in die Kombinatorik. de Gruyter, Berlin (u. a.) 1983, ISBN 3-11-008736-7.
  •  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
  •  Dieter Jungnickel: Transversaltheorie. Akad. Verl.-Ges. Geest & Portig, Leipzig 1982.
  •  L. Lovász und M. D. Plummer: Matching Theory. North-Holland, Amsterdam (u.a.) 1986, ISBN 0-444-87916-1.
  •  Leonid Mirsky: Transversal Theory. Academic Press, New York, London 1971, ISBN 0-12-498550-5.

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1.  Dilworth in Annals of Mathematics, vol. 51,: S. 161 ff.
  2. Siehe hierzu Rado's Auswahlprinzip.
  3.  Jukna: S. 55.
  4.  Jukna: S. 55.
  5.  Jukna: S. 71.
  6. Siehe im englischsprachigen WIKIPEDIA: [1]
  7.  Jukna: S. 69.