Order dimension and weak poset partitions

Question

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.

Answer 1

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$.

Answer 2

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<j$, $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<i$. 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.)