Dilworth's theorem
The set of Dilworth is a mathematical theorem, which both the order theory and discrete mathematics is to be assigned. It goes back to a paper by Robert Palmer Dilworth from the year 1950. The set makes a fundamental statement about the interaction between chains and antichains in a partial order.
- 5.1 Original Article
- 5.2 monographs
The sentence in three versions
Let be a partially ordered set of finite ground set. Then:
First version
Second version
Third version
A chain is a subset in which all elements in the given order relation are pairwise comparable, ie applies for or always. In contrast, an anti- chain is a subset in which for any two distinct elements always true that they are not comparable in the given order relation, ie for with true and always.
Related phrases
- Hall's theorem (marriage record)
- König's theorem ( Graph Theory )
- Max -flow min-cut theorem
- Menger's theorem
- Set of Birkhoff and von Neumann
The sets of Dilworth, Hall, King, and Menger, and the Max -Flow Min -Cut Theorem to each other as theorems of discrete mathematics equivalent. This means that each of these five sets implies each other and is implied by this is so true if and only if the other is true. There is to this important and well- known relationship detailed descriptions in the literature (see below ), especially in young and nickel in the paper by Jacobs in Selecta Mathematica I.
The set of Birkhoff and von Neumann is a direct consequence of the theorem of Hall ( see Lovász and Plummer ) and is thus also implies by the theorem of Dilworth.
Of the two mathematicians Gallai and Milgram is a graph-theoretical sentence before - published 1960, see Diestel - which is similar and even more generally the set of Dilworth.
Extension to the infinite case
There are set of Dilworth (as well as the marriage theorem ) an enhanced version, which includes the case that the base set is infinite. However, the proof of this transfinite version is commonly referred to as a key tool in the lemma of Zorn a, ie proceeds from the axiom of choice.
Corollary: A set of Erdos and Szekeres
The set of Dilworth immediately pulls another known set of discrete mathematics by itself, which dates back to the work of Paul Erdős and George Szekeres in 1935. This set is considered to be one of the first results of the so-called extremal combinatorics (English extremal combinatorics ).
The set of Erdos and Szekeres states the following:
The derivation of the set of Dilworth results, by providing the crowd with the following partial ordering:
From the set of Dilworth it follows under the conditions mentioned mandatory that at least one chain of the number or an anti- chain of the number includes, which then results also everything else.
This set of Erdos and Szekeres connects to another set, which is connected to the ( in English literature ) called Happy Ending trouble and was also formulated by Erdos and Szekeres in the same work in 1935. This can be formulated as follows: