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:
“We know then the existence and nature of the finite, because we also are finite and have extension. We know the existence of the infinite and are ignorant of its nature, because it has extension like us, but not limits like us. But we know neither the existence nor the nature of God, because he has neither extension nor limits.”
—Blaise Pascal (1623–1662)
“In nature’s infinite book of secrecy
A little I can read.”
—William Shakespeare (1564–1616)
“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)
“Then he rang the bell and ordered a ham sandwich. When the maid placed the plate on the table, he deliberately looked away but as soon as the door had shut, he grabbed the sandwich with both hands, immediately soiled his fingers and chin with the hanging margin of fat and, grunting greedily, began to much.”
—Vladimir Nabokov (1899–1977)
“A horse, a buggy and several sets of harness, valued in all at about $250, were stolen last night from the stable of Howard Quinlan, near Kingsville. The county police are at work on the case, but so far no trace of either thieves or booty has been found.”
—H.L. (Henry Lewis)