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).