Dimension of a partially ordered set

From Encyclopedia of Mathematics
Revision as of 17:21, 7 February 2011 by (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

dimension of a poset

Let be a partially ordered set. A linear extension of is a total ordering (see also Totally ordered set) on such that is order preserving, i.e. such that in implies in . The existence of linear extensions was proved by E. Szpilrain, [a4], in 1931.

The dimension of a poset is the least for which there exists a family of linear extensions such that

A chain in is a partially ordered subset of (a sub-poset) that is totally ordered. An anti-chain in is a set of elements such that no , , , are comparable. The height of is the maximal length of a chain. The width of is the maximal size of an anti-chain. The Dilworth decomposition theorem says that if , then decomposes as the disjoint sum of chains (cf. Disjoint sum of partially ordered sets; cf. also (the editorial comments to) Partially ordered set). Using this, T. Hiraguchi [a2] proved

The concept was introduced by B. Dushnik and E.W. Miler [a1].


[a1] B. Dushnik, E.W. Miller, "Partially ordered sets" Amer. J. Math. , 63 (1941) pp. 600–610
[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
[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:
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article