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
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (210)
Orphanage
Unclass'd (1)
Unproven (472)
Corrections (37)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
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 MSC: 06A06 (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)