Order dimension

From Wikipedia, the free encyclopedia

A partial order of dimension 4 (shown as a Hasse diagram) and four total orderings that form a realizer for this partial order.
A partial order of dimension 4 (shown as a Hasse diagram) and four total orderings that form a realizer for this partial order.

In mathematics, the dimension of a partially ordered set (poset) is the smallest number of total orders the intersection of which gives rise to the partial order. This concept is also sometimes called the order dimension or the Dushnik–Miller dimension of the partial order. Dushnik & Miller (1941) first studied order dimension; for a more detailed treatment of this subject than provided here, see Trotter (1992).

Contents

[edit] Formal definition

The dimension of a poset P is the least integer t for which there exists a family

\mathcal R=(<_1,\dots,<_t)

of linear extensions of P so that, for every x and y in P, x precedes y in P if and only if it precedes y in each of the linear extensions. That is,

P=\bigcap\mathcal R=\bigcap_{i=1}^t <_i,

[edit] Realizers

A family \mathcal R=(<_1,\dots,<_t) of linear orders on X is called a realizer of P on X if

P=\bigcap\mathcal R.

It can be shown that R is a realizer if and only if, for every critical pair (x,y) of P, x <i y for some order <i in R.

[edit] Example

Let n be a positive integer, and let P be the partial order on the elements ai and bi (for 1 ≤ i ≤ n) in which ai ≤ bj whenever i ≠ j, and in which no other order relations exist. In particular, ai and bi are incomparable in P. The illustration shows an ordering of this type for n = 4.

Then, for each i, any realizer must contain a total ordering consisting of the elements aj (other than ai) first, in some order, then bi, then ai, followed finally by the elements bj (other than bi). For, if such an ordering were not included in the realizer, then the intersection of the total orderings would order ai before bi, contradicting their incomparability in P. And conversely, any family of orderings that includes one order of this type for each i has P as its intersection. Thus, P has order dimension exactly n. In fact, P is known as the standard example of a poset of dimension n, and is usually denoted by Sn.

[edit] References

  • Trotter, William T. (1992), Combinatorics and partially ordered sets: Dimension theory, Johns Hopkins series in the mathematical sciences, The Johns Hopkins University Press, ISBN 978-0801844256 .