Order Dimension

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).

Read more about Order DimensionFormal Definition, Realizers, Example, Order Dimension Two, Computational Complexity, Incidence Posets of Graphs, K-dimension and 2-dimension

Other articles related to "dimension, order dimension, order, orders":

Schnyder's Theorem - Extensions
... and Trotter (1993, 1997) to a tight bound on the dimension of the height-three partially ordered sets formed analogously from the vertices, edges and faces of a convex ... convex polytopes, as there exist four-dimensional polytopes whose face lattices have unbounded order dimension ... Even more generally, for abstract simplicial complexes, the order dimension of the face poset of the complex is at most 1 + d, where d is the minimum dimension of a Euclidean space in which the complex has a ...
Order Dimension - K-dimension and 2-dimension
... A generalization of dimension is the notion of k-dimension (written ) which is the minimal number of chains of length at most k in whose product the partial order can be embedded ... In particular, the 2-dimension of an order can be seen as the size of the smallest set such that the order embeds in the containment order on this set ...
Schnyder's Theorem - Other Graphs
... the incidence poset of a graph G has order dimension two if and only if the graph is a path or a subgraph of a path ... For, the only possible realizer for the incidence poset consists of two total orders that (when restricted to the graph's vertices) are the reverse of each ... But two total orders on the vertices that are the reverse of each other can realize any subgraph of a path, by including the edges of the path in the ordering immediately following the ...

Famous quotes containing the words dimension and/or order:

    Le Corbusier was the sort of relentlessly rational intellectual that only France loves wholeheartedly, the logician who flies higher and higher in ever-decreasing circles until, with one last, utterly inevitable induction, he disappears up his own fundamental aperture and emerges in the fourth dimension as a needle-thin umber bird.
    Tom Wolfe (b. 1931)

    Beauty is desired in order that it may be befouled; not for its own sake, but for the joy brought by the certainty of profaning it.
    Georges Bataille (1897–1962)