## You are here

Homedimension of a poset

## Primary tabs

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

## Mathematics Subject Classification

06A06*no label found*06A07

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections