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 $\lbrace L_1,\ldots, L_n\rbrace$ ).

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=\lbrace a_1,\ldots, a_m\rbrace$ 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 $\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$ .

Bibliography

1

W. T. Trotter, Combinatorics and Partially Ordered Sets, Johns-Hopkins University Press, Baltimore (1992).