2
$\begingroup$

A partial order $(X, <_X)$ has order dimension $n$ if it can be realized as the product order of $n$ total orders, which means that there is an order-embedding between $(X, \lt_X)$ and $(Y^n, \lt)$ for some totally ordered set $Y$, where we define $\lt$ as $\bigwedge_i \lt_{i,i}$. (The $\lt_{i,j}$ are the orders on tuples defined by $x \lt_{i,j} y$ iff $x_i \lt y_j$).

A partial order $(X, <_X)$ is an interval order if it can be realized as the interval precedence order on some set of intervals, which means that there is an order-embedding between $(X, \lt_X)$ and $(\mathbb{N}^2, \lt)$ where we define $\lt$ as $\lt_{1,1} \wedge \lt_{1,2} \wedge \lt_{2,1} \wedge \lt_{2,2}$.

Is there some generalization of these notions which looks at other ways to define a partial order on tuples from the $<_{i,j}$?

$\endgroup$
4
  • 2
    $\begingroup$ Judging from the way you employ $\mathbb N$ in these definitions instead of a general total order, I take it you are only interested in finite partial orders? $\endgroup$ Commented Sep 11, 2012 at 9:46
  • $\begingroup$ Ah, I did not pay attention to that. There's no point in restricting the scope of the question, so I rephrased. Thanks! $\endgroup$
    – a3nm
    Commented Sep 11, 2012 at 11:31
  • $\begingroup$ Since $(\mathbb{N}^2,{\lt_{1,2}})$ is not a partial order, what is an order-embedding into it? $\endgroup$ Commented Sep 11, 2012 at 12:11
  • $\begingroup$ François G. Dorais: Ah, I hadn't noticed that encoding the interval precedence order is trickier if you're working with couples of integers rather than intervals. Sorry for that, I have fixed the definition, hopefully it is correct now. $\endgroup$
    – a3nm
    Commented Sep 11, 2012 at 13:01

0

You must log in to answer this question.

Browse other questions tagged .