Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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}$?

share|improve this question
2  
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? –  Emil Jeřábek Sep 11 '12 at 9:46
    
Ah, I did not pay attention to that. There's no point in restricting the scope of the question, so I rephrased. Thanks! –  a3nm Sep 11 '12 at 11:31
    
Since $(\mathbb{N}^2,{\lt_{1,2}})$ is not a partial order, what is an order-embedding into it? –  François G. Dorais Sep 11 '12 at 12:11
    
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. –  a3nm Sep 11 '12 at 13:01
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.