MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The order dimension of a poset $(P,\leq)$ is the least number of linear extensions of $(P,\leq)$ such that the intersection of these extensions is $(P,\leq)$. The wikipedia entry provides some examples.

I know that there is quite a bit of research about this, but I haven't found anything concerning the following question:

Assume that $(P_1,\leq_1),\ldots,(P_n,\leq_n)$ are all partial orders and subspaces of $(P,\leq)$ such that they form a weak partition of $P$, that is, we have $\bigcup_i^n P_i = P$, but the posets are not necessarily pairwise disjoint.

As a variant of this, let us also consider the case in which we additionally require that $\leq$ is the smallest order-relation on $P$ that contains $\leq_1,\ldots,\leq_n$.

Assume that $P$ can be written as the weak partition of $n$ posets, where each of these posets has order dimension at most $k$. Does this tell us anything about the order dimension of $(P,\leq)$? Does it, perhaps, yield an upper bound? What if we take the variant?

Both cases are easy if all $n$ posets are pairwise disjoint or if $k =1$ (in which case it is just a covering of $(P,\leq)$ by chains). But it doesn't seem very easy if they intersect and we have $k \geq 2$, so I was wondering if anybody could point me towards some research that was done in this direction.

The case $k=2$ alone seems to be very interesting.

share|cite|improve this question
The link to Wikipedia should be fixed. – Samuele Giraudo Apr 15 '13 at 11:35
Thanks for pointing that out and sorry for that being necessary. I have fixed the link. – Niemi Apr 15 '13 at 11:41
Related question:… – François G. Dorais Apr 15 '13 at 19:24

Here is what I think is a partial answer to the problem.

Assuming that $(P_1,\leq_1),…,(P_n,\leq_n)$ are all subspaces of $(P,\leq)$ and $P_1,\ldots,P_n$ form a weak partition of $P$. If all $n$ spaces have order dimension at most $k$, this does not yield a bound on the order dimension of $(P,\leq)$ in general.

Of course, it does yield an upper bound if we have $k=1$. Then, $P_1,\ldots,P_n$ are chains and this is known to cause that the order dimension of $(P,\leq)$ is at most $k$ (in fact, this is one of the most fundemental facts about the order dimension).

However, as soon as we have $k=2$, this is not true anymore, even if we require that $(P,\leq)$ is connected and has top and bottom. Take, for instance, $P(n) = \{0,a_1,\ldots,a_n,b_1,\ldots,b_n,1\}$ and define $\leq$ to be the order given by $x \leq y$ for $x \neq y$ if and only $y = 1$ or $x=0$ or $x = a_i$ and $y = b_j$ for some $i \neq j$. Then, for each $n \in \mathbb{N}$, $P(n)$ can be covered by three subspaces $(P_1,\leq_1),(P_2,\leq_2),(P_3,\leq_3)$, each of which is a tree. Trees have order dimension $2$, so $P(n)$ can always be covered by three subspaces of order dimension $2$. But now, $(P(n),\leq)$ has order dimension $n$ (in fact, it is the poset that is obtained by adding a greatest and least element to what is often called the standard example of a poset of order dimension $n$).

This, however, does not answer the version with the variant in which the transitive closure of $\bigcup \leq_i$ has to be $\leq$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.