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, 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