Namespaces
Variants
Actions

Difference between revisions of "Dimension of a partially ordered set"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX done)
 
Line 1: Line 1:
 
''dimension of a poset''
 
''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.
+
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 mapping|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, [[#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
+
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 \ .
 +
$$
  
<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 $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 a partially ordered set|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 [[#References|[a2]]] proved
 +
$$
 +
\mathrm{dim}(P) \le \mathrm{width}(P) \ .
 +
$$
 +
The concept of dimension was introduced by B. Dushnik and E.W. Miler [[#References|[a1]]].
  
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
+
====References====
 
+
<table>
<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>
+
<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 {{DOI|10.2307/2371374}} {{ZBL|0025.31002}}</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>
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]]].
+
<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 {{ZBL|56.0843.02}}</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>
  
====References====
+
{{TEX|done}}
<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>
 

Latest revision as of 15:27, 10 January 2016

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://encyclopediaofmath.org/index.php?title=Dimension_of_a_partially_ordered_set&oldid=37445
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article