11
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ The link to Wikipedia should be fixed. $\endgroup$ Apr 15, 2013 at 11:35
  • $\begingroup$ Thanks for pointing that out and sorry for that being necessary. I have fixed the link. $\endgroup$
    – Niemi
    Apr 15, 2013 at 11:41
  • $\begingroup$ Related question: mathoverflow.net/questions/29169/… $\endgroup$ Apr 15, 2013 at 19:24

2 Answers 2

3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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