View source for Dimension of a partially ordered set

''dimension of a poset''

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120170/d1201701.png" /> be a [[Partially ordered set|partially ordered set]]. A linear extension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120170/d1201702.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120170/d1201703.png" /> is a total ordering <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120170/d1201704.png" /> (see also [[Totally ordered set|Totally ordered set]]) on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120170/d1201705.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120170/d1201706.png" /> is order preserving, i.e. such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120170/d1201707.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120170/d1201708.png" /> implies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120170/d1201709.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120170/d12017010.png" />. The existence of linear extensions was proved by E. Szpilrain, [[#References|[a4]]], in 1931.

The dimension of a poset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120170/d12017011.png" /> is the least <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120170/d12017012.png" /> for which there exists a family of linear extensions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120170/d12017013.png" /> such that

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120170/d12017014.png" /></td> </tr></table>

A chain in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120170/d12017015.png" /> is a partially ordered subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120170/d12017016.png" /> (a sub-poset) that is totally ordered. An anti-chain in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120170/d12017017.png" /> is a set of elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120170/d12017018.png" /> such that no <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120170/d12017019.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120170/d12017020.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120170/d12017021.png" />, are comparable. The height of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120170/d12017022.png" /> is the maximal length of a chain. The width of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120170/d12017023.png" /> is the maximal size of an anti-chain. The Dilworth decomposition theorem says that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120170/d12017024.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120170/d12017025.png" /> decomposes as the disjoint sum of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120170/d12017026.png" /> chains (cf. [[Disjoint sum of partially ordered sets|Disjoint sum of partially ordered sets]]; cf. also (the editorial comments to) [[Partially ordered set|Partially ordered set]]). Using this, T. Hiraguchi [[#References|[a2]]] proved

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120170/d12017027.png" /></td> </tr></table>

The concept <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120170/d12017028.png" /> was introduced by B. Dushnik and E.W. Miler [[#References|[a1]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  B. Dushnik,   E.W. Miller,   "Partially ordered sets"  ''Amer. J. Math.'' , '''63'''  (1941)  pp. 600–610</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  T. Hiraguchi,   "On the dimension of partially ordered sets"  ''Sci. Rep. Kanazawa Univ.'' , '''1'''  (1951)  pp. 77–94</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  D. Kelley,   W.T. Trotter,   "Dimension theory for ordered sets"  I. Rival (ed.) , ''Ordered Sets'' , Reidel  (1987)  pp. 171–212</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  E. [E. Szpilrain] Szpilrajn,   "Sur l'extension de l'ordre partiel"  ''Fund. Math.'' , '''16'''  (1930)  pp. 386–389</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  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</TD></TR></table>