dimension of a poset
Let $P$ be a finite poset and $\mathcal{R}$ be the family of all realizers^{} of $P$. The dimension^{} of $P$, written $\mathrm{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},\mathrm{\dots},{L}_{n}$ of $P$ such that $P={L}_{1}\cap \mathrm{\cdots}\cap {L}_{n}$. ($E$ can be chosen to be $\{{L}_{1},\mathrm{\dots},{L}_{n}\}$).
If $P$ is a chain, then $\mathrm{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=\{{a}_{1},\mathrm{\dots},{a}_{m}\}$ 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 $\mathrm{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$.
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 |