Kruskal's theorem

The set of Kruskal is a theorem of graph theory , one of the branches of mathematics . It was developed by the mathematician Joseph Bernard Kruskal in 1960 published . The theorem deals with an important property of the class of finite trees .

Formulation of the sentence

The sentence can be stated as follows:

The class of finite trees is well -quasi-ordered through the quasi-order relation of the formation of topological minors .

In other words: Every countable set of finite trees, together with the topological minor relation, forms a well-founded, quasi- ordered set in which every anti-chain is finite.

Related sentences

Kruskal's theorem was generalized to infinite trees by Crispin St. JA Nash-Williams in the 1960s . Daniela Kühn presented a simplified proof of both theorems in 2001. The Kruskal theorem is tied into the problem area around the important minor theorem .

literature

Original work

• JB Kruskal: Well-quasi-ordering, the Tree Theorem, and Vazsonyi's conjecture . In: Transactions of the American Mathematical Society . tape 95 , 1960, pp. 210-225 ( ams.org ). MR0111704
• Daniela Kühn: On well-quasi-ordering infinite trees — Nash-Williams's theorem revisited . In: Mathematical Proceedings of the Cambridge Philosophical Society . tape 130 , 2001, p. 401-408 . MR1816801
• C. St. JA Nash – Williams: On well-quasi-ordering infinite trees . In: Mathematical Proceedings of the Cambridge Philosophical Society . tape 61 , 1965, p. 697-720 . MR0175814
• C. St. JA Nash – Williams: On better-quasi-ordering transfinite sequences . In: Mathematical Proceedings of the Cambridge Philosophical Society . tape 64 , 1968, pp. 273-290 . MR0221949

Monographs

• Reinhard Diestel : graph theory . 2nd Edition. Springer Verlag , Berlin / Heidelberg / New York (and others) 2000, ISBN 3-540-67656-2 .
• Reinhard Diestel: Graph Theory (=  Graduate Texts in Mathematics . Volume 173 ). 3. Edition. Springer Verlag, Berlin / Heidelberg / New York 2005, ISBN 3-540-26182-6 ( MR2159259 ).
• Egbert Harzheim : Ordered Sets (=  Advances in Mathematics . Volume 7 ). Springer Verlag, New York 2005, ISBN 0-387-24219-8 . MR2127991
• Rudolf Halin : Graph Theory I (=  yields of research . Volume 138 ). Wissenschaftliche Buchgesellschaft, Darmstadt 1980, ISBN 3-534-06767-3 ( MR0586234 ).
• Klaus Wagner : Theory of graphs (=  BI university pocket books. 248 / 248a). Bibliographisches Institut, Mannheim ( inter alia ) 1970, ISBN 3-411-00248-4 ( MR0282850 ).

References and footnotes

1. ↑ Reinhard Diestel: Graph theory. 2000, pp. 251 ff., 253-255
2. ^ Reinhard Diestel: Graph Theory. 2005, p. 316 ff., 317
3. ^ ^{A b c} Egbert Harzheim: Ordered Sets. 2005, pp. 231 ff., 245-246
4. ^ Klaus Wagner: Graph theory. 1970, p. 172 ff., 178
5. ^ Rudolf Halin: Graphentheorie I. 1980, p. 116 ff.
6. ↑ Diestel, op.cit., P. 354