Order dimension

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 all of the linear extensions, if any such t exists.

of linear orders on X is called a realizer of a poset P = (X,

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

In particular, ai and bi are incomparable in P; P can be viewed as an oriented form of a crown graph.

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.

They are exactly the partial orders whose Hasse diagrams have dominance drawings, which can be obtained by using the positions in the two permutations of a realizer as Cartesian coordinates.

However, for any k ≥ 3, it is NP-complete to test whether the order dimension is at most k (Yannakakis 1982).

For a complete graph on n vertices, the order dimension of the incidence poset is

It follows that all simple n-vertex graphs have incidence posets with order dimension

) which is the minimal number of chains of length at most k in whose product the partial order can be embedded.