3
$\begingroup$

Let $(P,\leq)$ be a finit poset, $w$ its width. Then, by Dilworth's theorem, I know that $P$ is a union of $w$ chains.

My question is: is there also a relation between the order dimension of a poset and its width?

Thanks very much for the help. Also if there are any results that some how disciplines the order dimension of a poset based on any order relation's properties it would be of great help.

$\endgroup$

1 Answer 1

2
$\begingroup$

Dilworth also proved that the order dimension of a (finite) poset is less than or equal to its width. This was in the same paper as the result you quoted:

R. P. Dilworth, A decomposition theorem for partially ordered sets, Ann. Math. 51 (1950), 161–165.

(By the way, the same goes for infinite posets, provided the width is finite.)

Here is an outline of the proof. Suppose the (finite) poset $P$ has width $n.$ Then $P$ is the union of $n$ disjoint chains $C_1,\dots,C_n.$ (This is the tricky part but you already know it.) For each $i\in\{1,\dots,n\},$ extend the given partial order to a total order $\le_i$ so that,if $x,y$ are incomparable in $P$ and $y\in C_i,$ then $x\le_iy.$ (Exercise.) Then the given partial order is the intersection of the $n$ total orders $\le_1,\dots,\le_n.$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .