# Dimension of a partially ordered set

*dimension of a poset*

Let $P = (X,{\le})$ be a partially ordered set. A linear extension $L$ of $P$ is a total ordering $\le_1$ (see also Totally ordered set) on $X$ such that $\mathrm{id} : P \rightarrow L$ is order preserving, i.e. such that $x \le y$ in $P$ implies $x \le_1 y$ in $L$. The existence of linear extensions was proved by E. Szpilrain, [a4], in 1931.

The *dimension* of a poset $P$ is the least $d$ for which there exists a family of linear extensions $L_1=(X,{\le_1}),\ldots,L_d=(X,{\le_d})$ such that
$$
x \le y \Leftrightarrow x \le_1 y,\ldots,x \le_d y \ .
$$

A chain in $P$ is a partially ordered subset of $P$ (a sub-poset) that is totally ordered. An anti-chain in $P$ is a set of elements $x_1,\ldots,x_n$ such that no $x_i, x_j$, $i \ne j$, are comparable. The *height* of $P$ is the maximal length of a chain. The *width* of $P$ is the maximal size of an anti-chain. The Dilworth decomposition theorem says that if $\mathrm{width}(P) = w$, then $P$ decomposes as the disjoint sum of $d$ chains (cf. Disjoint sum of partially ordered sets; cf. also (the editorial comments to) Partially ordered set). Using this, T. Hiraguchi [a2] proved
$$
\mathrm{dim}(P) \le \mathrm{width}(P) \ .
$$
The concept of dimension was introduced by B. Dushnik and E.W. Miler [a1].

#### References

[a1] | B. Dushnik, E.W. Miller, "Partially ordered sets" Amer. J. Math. , 63 (1941) pp. 600–610 DOI 10.2307/2371374 Zbl 0025.31002 |

[a2] | T. Hiraguchi, "On the dimension of partially ordered sets" Sci. Rep. Kanazawa Univ. , 1 (1951) pp. 77–94 |

[a3] | D. Kelley, W.T. Trotter, "Dimension theory for ordered sets" I. Rival (ed.) , Ordered Sets , Reidel (1987) pp. 171–212 |

[a4] | E. [E. Szpilrain] Szpilrajn, "Sur l'extension de l'ordre partiel" Fund. Math. , 16 (1930) pp. 386–389 Zbl 56.0843.02 |

[a5] | W.T. Trotter, "Partially ordered sets" R.L. Graham (ed.) M. Grötschel (ed.) L. Lovász (ed.) , Handbook of Combinatorics , I , North-Holland (1995) pp. 433–480 |

**How to Cite This Entry:**

Dimension of a partially ordered set.

*Encyclopedia of Mathematics.*URL: http://www.encyclopediaofmath.org/index.php?title=Dimension_of_a_partially_ordered_set&oldid=37445