Extension To Infinite Partially Ordered Sets
Dilworth's theorem for infinite partially ordered sets states that a partially ordered set has finite width w if and only if may be partitioned into w chains. For, suppose that an infinite partial order P has width w, meaning that there are at most a finite number w of elements in any antichain. For any subset S of P, a decomposition into w chains (if it exists) may be described as a coloring of the incomparability graph of S (a graph that has the elements of S as vertices, with an edge between every two incomparable elements) using w colors; every color class in a proper coloring of the incomparability graph must be a chain. By the assumption that P has width w, and by the finite version of Dilworth's theorem, every finite subset S of P has a w-colorable incomparability graph. Therefore, by the De Bruijn–Erdős theorem, P itself also has a w-colorable incomparability graph, and thus has the desired partition into chains (Harzheim 2005).
However, the theorem does not extend so simply to partially ordered sets in which the width, and not just the cardinality of the set, is infinite. In this case the size of the largest antichain and the minimum number of chains needed to cover the partial order may be very different from each other. In particular, for every infinite cardinal number κ there is an infinite partially ordered set of width ℵ0 whose partition into the fewest chains has κ chains (Harzheim 2005).
Perles (1963) discusses analogs of Dilworth's theorem in the infinite setting.
Read more about this topic: Dilworth's Theorem
Famous quotes containing the words extension, infinite, partially, ordered and/or sets:
“The medium is the message. This is merely to say that the personal and social consequences of any medium—that is, of any extension of ourselves—result from the new scale that is introduced into our affairs by each extension of ourselves, or by any new technology.”
—Marshall McLuhan (1911–1980)
“So that if you would form a just judgment of what is of infinite importance to you not to be misled in,—namely, in what degree of real merit you stand ... call in religion and morality.—Look,—What is written in the law of God?—How readest thou?—Consult calm reason and the unchangeable obligations of justice and truth;Mwhat say they?”
—Laurence Sterne (1713–1768)
“Some men have a necessity to be mean, as if they were exercising a faculty which they had to partially neglect since early childhood.”
—F. Scott Fitzgerald (1896–1940)
“Twenty-four-hour room service generally refers to the length of time that it takes for the club sandwich to arrive. This is indeed disheartening, particularly when you’ve ordered scrambled eggs.”
—Fran Lebowitz (b. 1950)
“bars of that strange speech
In which each sound sets out to seek each other,
Murders its own father, marries its own mother,
And ends as one grand transcendental vowel.”
—Randall Jarrell (1914–1965)