Dilworth theorem

The set of Dilworth is a mathematical theorem , which both the order theory and the discrete mathematics belongs. It is considered to be one of the fundamental theorems of the so-called matching theory .

The sentence goes back to a work by Robert Palmer Dilworth from 1950. It makes a fundamental statement about the interaction between chains and anti- chains in a partial order .

The set in four versions

Let be a partial order with a finite basic set . Then: ${\displaystyle (P,\leq )}$ ${\displaystyle P\,}$

First version

The greatest thickness of an anti- chain of is equal to the smallest number of chains that form a disjoint decomposition of the basic set . ${\displaystyle (P,\leq )}$ ${\displaystyle P\,}$

Second version

Is     the Spernerzahl of    , then the base quantity can     in     chains     disjoint disassemble: ${\displaystyle n\,}$ ${\displaystyle (P,\leq )}$ ${\displaystyle P\,}$ ${\displaystyle n\,}$ ${\displaystyle C_{1},\dots ,C_{n}}$

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

Vice versa:

If     the smallest number of chains , which form a disjoint decomposition of the basic set     , then has     the Sperner number   . ${\displaystyle n\,}$ ${\displaystyle P\,}$ ${\displaystyle (P,\leq )}$   ${\displaystyle n\,}$

Third version

There is a disjoint decomposition of the basic set   into chains and a system of representatives , which at the same time forms an anti- chain of . ${\displaystyle P\,}$ ${\displaystyle (P,\leq )}$

Fourth version

If there is no anti- chain of the number , the basic set can always be represented as a union of chains. ${\displaystyle (P,\leq )}$ ${\displaystyle m+1}$  ${\displaystyle (m\in \mathbb {N} _{0})}$ ${\displaystyle P}$ ${\displaystyle m}$

Explanations

1. A chain is a subset , which is characterized by the fact that all elements in the given half-order relation are comparable in pairs, i. H. for always applies or . ${\displaystyle C\subseteq (P,\leq )}$ ${\displaystyle a,b\in C}$ ${\displaystyle a\leq b}$ ${\displaystyle b\leq a}$
2. On the other hand, an anti-chain of is characterized by the fact that two different elements in it are “not” comparable in the given partial order relation; H. for with always applies and . ${\displaystyle (P,\leq )}$ ${\displaystyle a,b\in A}$ ${\displaystyle a\neq b}$ ${\displaystyle a\not \leq b}$ ${\displaystyle b\not \leq a}$
3. Chains such as anti-chains are inherited ; H. every subset of a chain or anti-chain is itself one.
4. The empty set and one-element sets are always chains and anti-chains at the same time. ${\displaystyle \emptyset }$
5. The fact that a chain and an anti-chain never intersect in more than one element is essential for many conclusions of order theory, i.e. that the intersection of a chain with an anti-chain is always either the empty set or a single-element set.
6. The basic set is the union of its one-element subsets; d. H. it applies . It is therefore certain that there is always at least one disjoint decomposition that consists of chains of . Because of the finiteness assumption, it is further ensured that a disjoint decomposition consisting of all such chains always has the smallest number. Some authors also call this number the “Dilworth number” of . Dilworth's theorem says that “for finite partial orders Sperner number and Dilworth number are identical”. ${\displaystyle P}$ ${\displaystyle P=\bigcup _{p\in P}\{p\}}$ ${\displaystyle P}$ ${\displaystyle (P,\leq )}$ ${\displaystyle P}$ ${\displaystyle (P,\leq )}$

For proof

There are a number of evidences for the theorem. In the more recent specialist literature, the evidence of Fred Galvin is often used , which is characterized by its particular brevity. The proof of Helge Tverberg is also often found in the specialist literature , which makes the structure of partial orders particularly clear and is also brief. Tverberg's proof draws on Micha Perles' idea of ​​proof and refines it. This proof is outlined below.

Evidence sketch after Perles and Tverberg

Dilworth's theorem is proved in its fourth version by complete induction on the number of elements of : ${\displaystyle |P|}$ ${\displaystyle P}$

In the case , nothing further needs to be shown, since the empty set can always be represented as the union of any number of copies of itself. ${\displaystyle |P|=0}$

The induction assumption now applies that and that the theorem is already valid for all finite partial orders of a number . ${\displaystyle |P|>0}$ ${\displaystyle <|P|}$

Then it can first be concluded that it has to be. Otherwise the assumption would result in the fact that it does not contain any elements and thus would be what contradicts the induction assumption . ${\displaystyle m>0}$ ${\displaystyle P}$ ${\displaystyle |P|=0}$

Furthermore, for reasons of finiteness , there is a maximal chain, i.e. a chain which has no other chain as a real superset . ${\displaystyle P}$ ${\displaystyle C}$ ${\displaystyle P}$

The largest element of will be labeled with , the smallest with . Apparently there is a maximal element and a minimal element of . Otherwise the chain could be extended by one element, i.e. it would have a different chain as a superset - in contradiction to its maximality. ${\displaystyle C}$ ${\displaystyle c^{+}}$ ${\displaystyle c^{-}}$ ${\displaystyle c^{+}}$ ${\displaystyle c^{-}}$ ${\displaystyle P}$ ${\displaystyle C}$

A distinction is made between two cases for: ${\displaystyle P\setminus C}$

case 1

There is no anti-chain with elements in. ${\displaystyle P\setminus C}$ ${\displaystyle m}$

Then due and the induction hypothesis union of chains and consequently as a union of represented chains. ${\displaystyle m=(m-1)+1}$ ${\displaystyle P\setminus C}$ ${\displaystyle m-1}$ ${\displaystyle P=(P\setminus C)\cup C}$ ${\displaystyle m}$

Case 2

There is an anti-chain with exactly the elements . ${\displaystyle P\setminus C}$ ${\displaystyle A=\{a_{1},\cdots ,a_{m}\}}$ ${\displaystyle m}$ ${\displaystyle (m\in \mathbb {N} )}$

This anti-chain has the property that each element of is comparable with at least one of its elements. Otherwise there would be a contradiction to the requirement that there is no anti-chain with elements. ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle m+1}$

Consequently, in the form ${\displaystyle P}$

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

represent with

${\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}\}}$   .

${\displaystyle A}$is equal to the set of maximum elements of as well as the set of minimum elements of , where obviously ${\displaystyle P^{-}}$ ${\displaystyle P^{+}}$

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

is.

So follow on and at the same time . Hence both and . ${\displaystyle c^{+}\in P^{+}\setminus P^{-}}$ ${\displaystyle c^{-}\in P^{-}\setminus P^{+}}$ ${\displaystyle |P^{-}|<|P|}$ ${\displaystyle |P^{+}|<|P|}$

According to the induction hypothesis, chains and can be found which contain the equations ${\displaystyle {C_{1}}^{-},\cdots ,{C_{m}}^{-}}$ ${\displaystyle {C_{1}}^{+},\cdots ,{C_{m}}^{+}}$

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

and

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

fulfill. Their indexing can be chosen in such a way that for each one is the largest element of and the smallest element of . ${\displaystyle i\in \{1,\cdots ,m\}}$   ${\displaystyle a_{i}}$ ${\displaystyle {C_{i}}^{-}}$ ${\displaystyle {C_{i}}^{+}}$

Is added for each and together by means of association so created new chains ${\displaystyle i\in \{1,\cdots ,m\}}$ ${\displaystyle {C_{i}}^{-}}$ ${\displaystyle {C_{i}}^{+}}$ ${\displaystyle m}$

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

from . ${\displaystyle P}$

With these now results in total

${\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}}$

and thus the conclusion that can be represented as a union of chains. ${\displaystyle P}$ ${\displaystyle m}$

This completes the induction step and the proof.

Related sentences

• Hall's Theorem ( marriage theorem )
• König's Theorem (graph theory)
• Max-flow-min-cut theorem
• Menger's theorem
• Birkhoff-von Neumann theorem

The theorems of Dilworth, Hall, König and Menger as well as the Max-Flow-Min-Cut theorem are equivalent to each other as theorems of discrete mathematics in the sense that each of these theorems can be easily derived from each of the others.

The Birkhoff-von Neumann theorem is a direct consequence of the Hall theorem and is thus also implied by the Dilworth theorem.

A graph-theoretical theorem from the two mathematicians Gallai and Milgram is available - published in 1960 - which is similar to Dilworth's theorem and even somewhat more general.

Derivation of the marriage theorem from Dilworth's theorem

The close relationships between the five mentioned sentences (theorems of Dilworth, Hall, König and Menger as well as the Max-Flow-Min-Cut theorem) become clear from the derivations, with which it is shown that each one leads to each other. An example of this is the derivation of the marriage theorem from Dilworth's theorem, which can be represented as follows:

Given a finite index set and a family of finite sets that meet the Hall condition ${\displaystyle I}$ ${\displaystyle {\mathcal {A}}=(A_{i})_{i\in I}}$

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

enough. It may be assumed that the union

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

and the index set are disjoint. ${\displaystyle I}$

To do this, the amount is determined using ${\displaystyle P}$

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

and on this the following partial order relation  : ${\displaystyle \leq }$

For applies if and only if ${\displaystyle p,q\in P}$ ${\displaystyle p\leq q}$

${\displaystyle p=q}$ or and and . ${\displaystyle p\in X}$ ${\displaystyle q\in I}$ ${\displaystyle p\in A_{q}}$

It is evident that it possesses partial order properties, and likewise that an anti-chain is of. It is of fundamental importance that because of the Hall condition in there is no anti-chain with more elements than exists. This shows the following consideration: ${\displaystyle \leq }$ ${\displaystyle X}$ ${\displaystyle (P,\leq )}$ ${\displaystyle (P,\leq )}$ ${\displaystyle U}$ ${\displaystyle X}$

Suppose there is an anti chain with . For these, the subset outside of is the same . The anti-chain property of means that a relationship can never exist for one element and for one . ${\displaystyle U}$ ${\displaystyle |U|>|X|}$ ${\displaystyle X}$ ${\displaystyle U\cap I}$ ${\displaystyle U}$ ${\displaystyle x\in U\cap X}$ ${\displaystyle k\in U\cap I}$ ${\displaystyle x\in A_{k}}$

This results in

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

and along with (H) further

${\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|}$

and in this way a contradiction.

That means: has the Sperner number . ${\displaystyle (P,\leq )}$ ${\displaystyle |X|}$

According to Dilworth's theorem, therefore, has a disjoint decomposition ${\displaystyle P}$

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

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

Due to the definition of , they all consist of at most two elements. That means: can be divided into the set of those elements from with and into the set of those elements from with . ${\displaystyle (P,\leq )}$ ${\displaystyle C_{x}}$ ${\displaystyle X}$ ${\displaystyle X_{1}}$ ${\displaystyle X}$ ${\displaystyle |C_{x}|=1}$ ${\displaystyle X_{2}}$ ${\displaystyle X}$ ${\displaystyle |C_{x}|=2}$

It must now be taken into account that each index is covered by exactly one of these chains . This means that the subset in a bijective correspondence with the index set is where to each element clearly reversibly an index with ${\displaystyle i\in I}$ ${\displaystyle C_{x}}$ ${\displaystyle X_{2}}$ ${\displaystyle I}$ ${\displaystyle x\in X_{2}}$ ${\displaystyle j(x)\in I}$

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

heard.

The bijection now delivers the desired injective selection function. Namely, one takes the inverse mapping , which is apparently always for the relationship ${\displaystyle j\colon X_{2}\to I}$ ${\displaystyle a:=j^{-1}\colon I\to X_{2}}$ ${\displaystyle i\in I}$

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

Fulfills.

The family given in this way is therefore a complete system of pairwise different representatives for the set family . ${\displaystyle (a(i))_{i\in I}}$ ${\displaystyle {\mathcal {A}}=(A_{i})_{i\in I}}$

Overall, this shows that Dilworth's Theorem entails the Marriage Theorem.

Extension to the infinite fall

There is an extended version of Dilworth's theorem (and also of the marriage theorem ), which includes the case that the basic set can also be infinite , but the Sperner number is still a natural number. The proof of this transfinite version , however, usually uses the lemma of Zorn as a decisive aid , thus presupposes the validity of the axiom of choice .

See also : Rado's selection principle

Corollary: A sentence by Erdős and Szekeres

Dilworth's theorem immediately leads to another well-known theorem of discrete mathematics , which goes back to a work by Paul Erdős and George Szekeres from 1935. This set is considered as one of the first results of the so-called extremal combinatorics (engl. Extremal combinatorics ).

The "Theorem of Erdős and Szekeres" says the following:

Let     and be there     and be     a finite sequence of     different real numbers in any order . ${\displaystyle n,r,s\in \mathbb {N} }$ ${\displaystyle n\geq {r\cdot s+1}}$ ${\displaystyle (a_{1},a_{2},\ldots ,a_{n})}$ ${\displaystyle n}$

Then contains   ${\displaystyle (a_{1},a_{2},\ldots ,a_{n})}$  

a partial sequence     with   ${\displaystyle (a_{n_{1}},a_{n_{2}},\ldots ,a_{n_{r+1}})}$ ${\displaystyle a_{n_{1}}<a_{n_{2}}<\ldots <a_{n_{r+1}}}$  

or

a partial sequence     with     . ${\displaystyle (a_{n_{1}},a_{n_{2}},\ldots ,a_{n_{s+1}})}$ ${\displaystyle a_{n_{1}}>a_{n_{2}}>\ldots >a_{n_{s+1}}}$

The derivation from Dilworth's Theorem results from providing the set     with the following partial order relation: ${\displaystyle P=\{a_{1},a_{2},\ldots ,a_{n}\}}$ ${\displaystyle {\leq }^{*}}$

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

It follows from Dilworth's theorem under the conditions mentioned that     at least one chain of the number   or an anti- chain of   the number     includes, which then also results in everything else. ${\displaystyle (P,{\leq }^{*})}$   ${\displaystyle r+1}$ ${\displaystyle s+1}$

This sentence by Erdős and Szekeres follows on from another sentence, which is connected with the so-called happy ending problem (in English literature) and which was also formulated by Erdős and Szekeres in the same work in 1935. This can be formulated as follows:

For any given number     one always finds a convex m-gon in the Euclidean plane within a sufficiently large set of finitely many points in a general position . ${\displaystyle m\in \mathbb {N} }$     ${\displaystyle (m\geq 3)}$

literature

Original article

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

Monographs

• Reinhard Diestel : Graph Theory . Springer, New York (et al.) 1997, ISBN 0-387-98211-6 .
• Egbert Harzheim : Ordered Sets (=  Advances in Mathematics . Volume 7 ). Springer Verlag, New York, NY 2005, ISBN 0-387-24219-8 ( MR2127991 ).
• Konrad Jacobs (Ed.): Selecta Mathematica I (=  Heidelberg Pocket Books . Volume 49 ). Springer-Verlag, Berlin / Heidelberg / New York 1969, p. 103-141 .
• Konrad Jacobs: Introduction to combinatorics (=  de Gruyter textbook ). de Gruyter, Berlin ( inter alia ) 1983, ISBN 3-11-008736-7 ( MR0720054 ).
• Dieter Jungnickel : Transversal Theory (=  mathematics and its applications in physics and technology . Volume 39 ). Academic publishing company Geest & Portig K.-G., Leipzig 1982 ( MR0706076 ).
• Stasys Jukna : Extremal Combinatorics (=  Texts in Theoretical Computer Science ). Springer Verlag, Heidelberg (among others) 2011, ISBN 978-3-642-17363-9 ( MR2865719 ).
• Joseph PS Kung, Gian-Carlo Rota , Catherine H. Yan: Combinatorics: The Rota Way (=  Cambridge Mathematical Library ). Cambridge University Press, Cambridge (et al.) 2009, ISBN 978-0-521-73794-4 ( MR2483561 ).
• L. Lovász and MD Plummer: Matching Theory (=  North-Holland Mathematics Studies . Volume 121 ). North-Holland, Amsterdam ( inter alia ) 1986, ISBN 0-444-87916-1 ( MR0859549 ).
• Leonid Mirsky : Transversal Theory (=  North-Holland Mathematics Studies . Volume 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 ).

Web links

• Combinatorial methods in computer science (PDF; 1.4 MB - script of a lecture by Peter Hauck, Uni Tübingen, SS 2008)
• Dilworth's Theorem on PlanetMath
• Dilworth's Lemma on MathWorld
• Piotr Rudnicki: Dilworth's Decomposition Theorem for Posets . In: Formalized Mathematics . tape 17 , no. 4 . University of Alberta, 2009, ISSN  1898-9934 , doi : 10.2478 / v10037-009-0028-4 ( citeseerx.ist.psu.edu - Additional article on Dilworth's theorem).

References and footnotes

1. ↑ Kung-Rota-Yan: p. 126.
2. ↑ The matching theory belongs - besides other important sentences - especially the famous marriage sentence by Philip Hall .
3. ^ Dilworth: Annals of Mathematics . tape 51 , p. 161 ff .
4. ↑ For finite sets, number and cardinality have the same meaning.
5. ↑ In this fourth version it cannot be ruled out that the chains and anti-chains as well as the basic set are equal to the empty set . ${\displaystyle P}$
6. ↑ For this is the empty union. ${\displaystyle P=\emptyset }$
7. ↑ The situation is different for infinite partial orders. The only general rule here is that the thickness of an anti-chain can never exceed the thickness of a chain decomposition; see. Harzheim: pp. 60-61.
8. ↑ In the following, instead of is written and in a corresponding manner for all subsets of . The semi-order relation is therefore assumed to be fixed in and in all subsets. ${\displaystyle P}$ ${\displaystyle (P,\leq )}$ ${\displaystyle P}$ ${\displaystyle \leq }$ ${\displaystyle P}$
9. ↑ For example, one can ensure in a longest Select chain, so that one among all chains of the greatest is Number. There is such a thing because every chain can obviously consist of at most elements. It doesn't matter how you find this chain. The finiteness requirement alone ensures that there is such a thing. ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle |P|}$
10. ↑ Reg. the partial order relation   ! ${\displaystyle \leq }$
11. ↑ As always is synonymous with . ${\displaystyle q\geq p}$ ${\displaystyle p\leq q}$
12. ↑ There are detailed descriptions of this in Jungnickel (pp. 90–92), Jacobs (pp. 38–42) and in the contribution by Jacobs to Selecta Mathematica I (pp. 131–137).
13. ↑ Lovász-Plummer: pp. 35–36.
14. ^ Gallai-Milgram: Acta Sci. Math. (Szeged) . S. 183 .
15. ↑ Diestel: pp. 38–40.
16. ↑ The representation here follows in Selecta Mathematica I . S. 133 .
17. ↑ Harzheim: pp. 58-60.
18. ↑ ^{a b} Jukna: p. 55.
19. ↑ Jukna: p. 71.
20. ↑ Jukna: p. 69.