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 .
|Title||dimension of a poset|
|Date of creation||2013-03-22 16:33:29|
|Last modified on||2013-03-22 16:33:29|
|Last modified by||CWoo (3771)|