Width of Special Partial Orders
The Boolean lattice Bn is the power set of an n-element set X—essentially {1, 2, …, n}—ordered by inclusion. Sperner's theorem states that a maximum antichain of Bn has size at most
In other words, a largest family of incomparable subsets of X is obtained by selecting the subsets of X that have median size. The Lubell–Yamamoto–Meshalkin inequality also concerns antichains in a power set and can be used to prove Sperner's theorem.
If we order the integers in the interval by divisibility, the subinterval forms an antichain with cardinality n. A partition of this partial order into n chains is easy to achieve: for each odd integer m in, form a chain of the numbers of the form m2i. Therefore, by Dilworth's theorem, the width of this partial order is n. Abouabdillah's theorem characterizes the integers that can belong to maximum antichains in this order.
The Erdős–Szekeres theorem on monotone subsequences can be interpreted as an application of Dilworth's theorem to partial orders of order dimension two (Steele 1995).
The "convex dimension" of an antimatroid is defined as the minimum number of chains needed to define the antimatroid, and Dilworth's theorem can be used to show that it equals the width of an associated partial order; this connection leads to a polynomial time algorithm for convex dimension (Edelman & Saks 1988).
Read more about this topic: Dilworth's Theorem
Famous quotes containing the words width of, width, special, partial and/or orders:
“Newly stumbling to and fro
All they find, outside the fold,
Is a wretched width of cold.”
—Philip Larkin (1922–1986)
“Newly stumbling to and fro
All they find, outside the fold,
Is a wretched width of cold.”
—Philip Larkin (1922–1986)
“The rebellion is against time pollution, the feeling that the essence of what makes life worth living—the small moments, the special family getaways, the cookies in the oven, the weekend drives, the long dreamlike summers Mso much of this has been taken from us, or we have given it up. For what? Hitachi stereos? Club Med? Company cars? Racquetball? For fifteen-hour days and lousy day care?”
—Richard Louv (20th century)
“There is no luck in literary reputation. They who make up the final verdict upon every book are not the partial and noisy readers of the hour when it appears; but a court as of angels, a public not to be bribed, not to be entreated, and not to be overawed, decides upon every man’s title to fame. Only those books come down which deserve to last.”
—Ralph Waldo Emerson (1803–1882)
“Our own physical body possesses a wisdom which we who inhabit the body lack. We give it orders which make no sense.”
—Henry Miller (1891–1980)