MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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

Your Answer


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

Browse other questions tagged or ask your own question.