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 Dimension: Formal Definition, Realizers, Example, Order Dimension Two, Computational Complexity, Incidence Posets of Graphs, K-dimension and 2-dimension
Other articles related to "order dimension, orders, dimension, order":
... As Schnyder observes, 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 ... 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 other otherwise, the intersection of the two ... 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 later of the two edge endpoints ...
... generalized by Brightwell and Trotter (1993, 1997) to a tight bound on the dimension of the height-three partially ordered sets formed analogously ... 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 ...
... 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 ...
Famous quotes containing the words dimension and/or order:
“Authority is the spiritual dimension of power because it depends upon faith in a system of meaning that decrees the necessity of the hierarchical order and so provides for the unity of imperative control.”
—Shoshana Zuboff (b. 1951)
“They are the lovers of law and order who observe the law when the government breaks it.”
—Henry David Thoreau (1817–1862)