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:
“Slavery is founded on the selfishness of man’s nature—opposition to it on his love of justice. These principles are in eternal antagonism; and when brought into collision so fiercely as slavery extension brings them, shocks and throes and convulsions must ceaselessly follow.”
—Abraham Lincoln (1809–1865)
“One who pressed forward incessantly and never rested from his labors, who grew fast and made infinite demands on life, would always find himself in a new country or wilderness, and surrounded by the raw material of life. He would be climbing over the prostrate stems of primitive forest-trees.”
—Henry David Thoreau (1817–1862)
“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)
“The case of Andrews is really a very bad one, as appears by the record already before me. Yet before receiving this I had ordered his punishment commuted to imprisonment ... and had so telegraphed. I did this, not on any merit in the case, but because I am trying to evade the butchering business lately.”
—Abraham Lincoln (1809–1865)
“The moment a man sets his thoughts down on paper, however secretly, he is in a sense writing for publication.”
—Raymond Chandler (1888–1959)