Order dimension

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). 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). The dimension of a poset P is the least integer t for which there exists a family 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, An alternative definition of order dimension is as the minimal number of total orders such that P embeds to the product of these total orders for the componentwise ordering, in which x ≤ y {displaystyle xleq y} if and only if x i ≤ y i {displaystyle x_{i}leq y_{i}} for all i (Hiraguti 1955, Milner & Pouzet 1990). A family R = ( < 1 , … , < t ) {displaystyle {mathcal {R}}=(<_{1},dots ,<_{t})} of linear orders on X is called a realizer of a poset P = (X, <P) if which is to say that for any x and y in X,x <P y precisely when x <1 y, x <2 y, ..., and x <t y.Thus, an equivalent definition of the dimension of a poset P is 'the least cardinality of a realizer of P.' It can be shown that any nonempty family R of linear extensions is a realizer of a finite partially ordered set P if and only if, for every critical pair (x,y) of P, y <i x for some order<i in R. 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, but no other pairs are comparable. In particular, ai and bi are incomparable in P; P can be viewed as an oriented form of a crown graph. The illustration shows an ordering of this type for n = 4. Then, for each i, any realizer must contain a linear order that begins with all the aj except ai (in some order), then includes bi, then ai, and ends with all the remaining bj. This is so because if there were a realizer that didn't include such an order, then the intersection of that realizer's orders would have ai preceding bi, which would contradict the incomparability of ai and bi in P. And conversely, any family of linear orders that includes one order of this type for each i has P as its intersection. Thus, P has dimension exactly n. In fact, P is known as the standard example of a poset of dimension n, and is usually denoted by Sn.