|
|
|
Viewing Version
3
of
'dimension of a poset'
|
[ view 'dimension of a poset'
|
back to history
]
| Title of object: |
dimension of a poset |
| Canonical Name: |
DimensionOfAPoset |
| Type: |
Definition |
| Created on: |
2007-01-12 18:40:44 |
| Modified on: |
2007-01-12 19:09:23 |
| Classification: |
msc:06A06, msc:06A07 |
| Defines: |
dimension |
Revision comment (for changes between this and next version):
Preamble:
\usepackage{amssymb,amscd}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
\usepackage{xypic}
\usepackage{pst-plot}
\usepackage{psfrag}
% define commands here
|
Content:
Let $P$ be a finite poset and $\mathcal{R}$ be the family of all realizers of $P$. The \emph{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 $\lbrace L_1,\ldots, L_n\rbrace$).
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=\lbrace a_1,\ldots, a_m\rbrace$ is an antichain, then one way to linearly extend $P$ is to simply put $a_i\le a_j$ iff $i\le j$. Called this extension $L_1$. Another way to order $P$ is to reverse $L_1$, by $a_i\le a_j$ iff $j\le 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\le a_j$ in both $L_1$ and $L_2$, so that $i\le j$ and $j\le 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$.
\textbf{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$.
\begin{thebibliography}{8}
\bibitem{wt} W. T. Trotter, {\em Combinatorics and Partially Ordered Sets}, Johns-Hopkins University Press, Baltimore (1992).
\end{thebibliography} |
|
|
|
|
|
