dimension of a poset
Let P be a finite poset and ℛ be the family of all realizers of P. The dimension
of P, written dim(P), is the cardinality of a member E∈ℛ with the smallest cardinality. In other words, the dimension n of P is the least number of linear extensions L1,…,Ln of P such that P=L1∩⋯∩Ln. (E can be chosen to be {L1,…,Ln}).
If P is a chain, then 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={a1,…,am} is an antichain, then one way to linearly extend P is to simply put ai≤aj iff i≤j. Called this extension
L1. Another way to order P is to reverse L1, by ai≤aj iff j≤i. Call this L2. Note that L1 and L2 are duals of each other. Let L=L1∩L2. As both L1 and L2 are linear extensions of P, P⊆L. On the other hand, if (ai,aj)∈L, then ai≤aj in both L1 and L2, so that i≤j and j≤i, or i=j and whence ai=aj, which implies (ai,aj)=(ai,ai)∈P. L⊆P and thus 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 ℝn, considered as the n-fold product of posets, or chains of real numbers ℝ, is the dimension of P.
References
-
1
W. T. Trotter, Combinatorics and Partially Ordered Sets
, Johns-Hopkins University Press, Baltimore (1992).
Title | dimension of a poset |
---|---|
Canonical name | DimensionOfAPoset |
Date of creation | 2013-03-22 16:33:29 |
Last modified on | 2013-03-22 16:33:29 |
Owner | CWoo (3771) |
Last modified by | CWoo (3771) |
Numerical id | 7 |
Author | CWoo (3771) |
Entry type | Definition |
Classification | msc 06A06 |
Classification | msc 06A07 |
Defines | dimension |