dimension of a poset
Let be a finite poset and be the family of all realizers of . The dimension of , written , is the cardinality of a member with the smallest cardinality. In other words, the dimension of is the least number of linear extensions of such that . ( can be chosen to be ).
If is a chain, then . The converse is clearly true too. An example of a poset with dimension 2 is an antichain with at least elements. For if is an antichain, then one way to linearly extend is to simply put iff . Called this extension . Another way to order is to reverse , by iff . Call this . Note that and are duals of each other. Let . As both and are linear extensions of , . On the other hand, if , then in both and , so that and , or and whence , which implies . and thus .
Remark. Let be a finite poset. A theorem of Dushnik and Miller states that the smallest such that can be embedded in , considered as the -fold product of posets, or chains of real numbers , is the dimension of .
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 |