PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Very high Entry average rating: No information on entry rating
[parent] dimension of a poset (Definition)

Let $ P$ be a finite poset and $ \mathcal{R}$ be the family of all realizers of $ P$. The dimension of $ P$, written $ \operatorname{dim}(P)$, is the cardinality of a member $ E\in \mathcal{R}$ with the smallest cardinality. In other words, the dimension $ n$ of $ P$ is the least number of linear extensions $ L_1,\ldots,L_n$ of $ P$ such that $ P=L_1\cap \cdots \cap L_n$. ($ E$ can be chosen to be $ \lbrace L_1,\ldots, L_n\rbrace$).

If $ P$ is a chain, then $ \operatorname{dim}(P)=1$. The converse is clearly true too. An example of a poset with dimension 2 is an antichain with at least $ 2$ elements. For if $ P=\lbrace a_1,\ldots, a_m\rbrace$ is an antichain, then one way to linearly extend $ P$ is to simply put $ a_i\le a_j$ iff $ i\le j$. Called this extension $ L_1$. Another way to order $ P$ is to reverse $ L_1$, by $ a_i\le a_j$ iff $ j\le i$. Call this $ L_2$. Note that $ L_1$ and $ L_2$ are duals of each other. Let $ L=L_1\cap L_2$. As both $ L_1$ and $ L_2$ are linear extensions of $ P$, $ P\subseteq L$. On the other hand, if $ (a_i,a_j)\in L$, then $ a_i\le a_j$ in both $ L_1$ and $ L_2$, so that $ i\le j$ and $ j\le i$, or $ i=j$ and whence $ a_i=a_j$, which implies $ (a_i,a_j)=(a_i,a_i)\in P$. $ L\subseteq P$ and thus $ \operatorname{dim}(P)=2$.

Remark. Let $ P$ be a finite poset. A theorem of Dushnik and Miller states that the smallest $ n$ such that $ P$ can be embedded in $ \mathbb{R}^n$, considered as the $ n$-fold product of posets, or chains of real numbers $ \mathbb{R}$, is the dimension of $ P$.

Bibliography

1
W. T. Trotter, Combinatorics and Partially Ordered Sets, Johns-Hopkins University Press, Baltimore (1992).



"dimension of a poset" is owned by CWoo. [ full author list (2) ]
(view preamble)

View style:

Also defines:  dimension

This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: real numbers, product of posets, implies, order, extension, iff, antichain, converse, chain, linear extensions, least number, cardinality, realizers, poset, finite
There are 44 references to this entry.

This is version 4 of dimension of a poset, born on 2007-01-12, modified 2007-01-13.
Object id is 8744, canonical name is DimensionOfAPoset.
Accessed 1349 times total.

Classification:
AMS MSC06A06 (Order, lattices, ordered algebraic structures :: Ordered sets :: Partial order, general)
 06A07 (Order, lattices, ordered algebraic structures :: Ordered sets :: Combinatorics of partially ordered sets)

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)