# 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 $\operatorname{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},\ldots,L_{n}$ of $P$ such that $P=L_{1}\cap\cdots\cap L_{n}$. ($E$ can be chosen to be $\{L_{1},\ldots,L_{n}\}$).

If $P$ is a chain, then $\operatorname{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},\ldots,a_{m}\}$ is an antichain, then one way to linearly extend $P$ is to simply put $a_{i}\leq a_{j}$ iff $i\leq j$. Called this extension $L_{1}$. Another way to order $P$ is to reverse $L_{1}$, by $a_{i}\leq a_{j}$ iff $j\leq 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}\leq a_{j}$ in both $L_{1}$ and $L_{2}$, so that $i\leq j$ and $j\leq 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 $\operatorname{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, , Johns-Hopkins University Press, Baltimore (1992).
Title dimension of a poset DimensionOfAPoset 2013-03-22 16:33:29 2013-03-22 16:33:29 CWoo (3771) CWoo (3771) 7 CWoo (3771) Definition msc 06A06 msc 06A07 dimension