# Order dimension and weak poset partitions

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.

• The link to Wikipedia should be fixed. Apr 15 '13 at 11:35
• Thanks for pointing that out and sorry for that being necessary. I have fixed the link. Apr 15 '13 at 11:41
• Related question: mathoverflow.net/questions/29169/… 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 fundamental 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$$.

The dimension of posets whose partial order relation is the transitive closure of 2 partial order relations of dimension 2 is unbounded. Here are two examples.

Standard example:

$$S_n$$ is a poset with minimal elements $$a_1,...,a_n$$ and maximal elements $$b_1,...,b_n$$, where $$a_i\leq b_j\Leftrightarrow i\neq j$$. It has dimension $$n$$. Consider the two posets $$(P_1,\leq_1),(P_2,\leq_2)$$ with $$a_i\leq_1 b_j \Leftrightarrow i, $$a_i\leq_2 b_j \Leftrightarrow i>j$$. Both of these have dimension 2, for instance a realizer for $$\leq_1$$ is

$$L_1$$: $$b_1,a_1,b_2,...,a_n$$ $$L_2$$: $$a_n,a_{n-1},...,a_1,b_n,...,b_1$$

Incidence poset of the complete graph $$K_n$$:

$$I_n$$ is a poset with minimal elements $$[n]$$ and maximal elements $$[n] \choose 2$$ equipped with the inclusion order. Iterative application of Erdös-Szekeres gives $$\dim(I_n)\in\Omega(\log \log n)$$. You can also decompose this one in 2 posets of dimension 2. Just take $$i\leq_1 \{i,j\} \Leftrightarrow j>i$$, $$i\leq_2 \{i,j\} \Leftrightarrow j. These posets are upward forests and hence have dimension 2 as you mentioned in your earlier answer. (The dimension of general trees can be 3 though.)

Some background:

Your question is related to the concept of boolean dimension. For a definition and further insights about it, have a look at this paper of Trotter and Walczak: https://arxiv.org/pdf/1705.09167.pdf

Imagine a Poset $$(P,\leq)$$ can be decomposed into $$k$$ posets $$(P_1,\leq_1),...,(P_k,\leq_k)$$ of dimension at most $$d$$, s.t. $$\leq=\bigcup_{i\in[k]}\leq_i$$ (For height 2 posets, it is not necessary to take the transitive closure). Let $$L_{ij},j\in[d]$$ be the realizer of poset $$P_i,i\in[k]$$ and let $$L_{ij}(x,y)$$ be true if $$x$$ is before $$y$$ in $$L_{ij}$$. Then $$x\leq y\Leftrightarrow \bigvee_{i\in [k]} (x\leq_i y) \Leftrightarrow \bigvee_{i\in [k]} \bigwedge_{j\in [d]} L_{ij}(x,y)$$. Thus the boolean dimension is at most $$kd$$. Now it is known that the boolean dimension is unbounded for posets of height 2 so there are some posets that do not allow a decomposition into few posets of low dimension which would have been a nice follow-up question. However, high dimension does not imply high boolean dimension and in fact the two classes of posets I used have high dimension but low boolean dimension as shown in the paper I cited. (You can also use my arguments to show their boolean dimension is at most 4.)