Order dimension

From Wikipedia, the free encyclopedia

You have new messages (last change).

In mathematics, if P and Q are posets on the same set X, Q is an extension of P if x\leq y in P implies x\leq y in Q, for all x,y\in X. If Q is a linear order then it is a linear extension of P.

The dimension (or Dushnik-Miller dimension) \dim P of P is the least integer t for which there exists a family

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

of linear extensions of P so that

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

that is: such that x\leq y in P if and only if x\leq_i y for all 1\leq i\leq t.

This concept was introduced by Dushnik and Miller in 1941.

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.

[edit] Example

Let n be a positive integer. The standard example Sn of partial order of dimension n is the partial order of height two on

\{a_1,\dots,a_n,b_1,\dots,b_n\},

with minima

\{a_1,\dots,a_n\}, maxima \{b_1,\dots,b_n\}

and such that

\forall i,j,\quad (a_i<b_j)\iff(i\neq j).

[edit] References

  • B. Dushnik and E.W. Miller, Partially ordered sets, Amer. J. Math. 63 (1941), 600--610.
  • W.T. Trotter, Combinatorics and partially ordered sets: Dimension theory, Johns Hopkins series in the mathematical sciences, Johns Hopkins University Press, London, 1992.
Retrieved from "http://en.wikipedia.org../../../o/r/d/Order_dimension.html"