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)
“It is characteristic of the epistemological tradition to present us with partial scenarios and then to demand whole or categorical answers as it were.”
—Avrum Stroll (b. 1921)
“Let’s start with the three fundamental Rules of Robotics.... We have: one, a robot may not injure a human being, or, through inaction, allow a human being to come to harm. Two, a robot must obey the orders given it by human beings except where such orders would conflict with the First Law. And three, a robot must protect its own existence as long as such protection does not conflict with the First or Second Laws.”
—Isaac Asimov (1920–1992)