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

Let $P = (X, \le)$ be a partially-ordered set. Then the dimension of $P$ is the minimum number of total orders over $X$ whose intersection yields $P$. Alternately, the dimension of $P$ is the minimum dimension of an isomorphic embedding of $P$ into $R^d$ endowed with the dominance partial order: $(x_1, \ldots x_d) \preceq (y_1, \ldots, y_d)$ if for all $i$, $x_i \le y_i$.

The set of total orders (the realizers) that witness the dimension can be thought of as witnessing all possible legal pairwise orderings in any linear extension of $P$: if $a, b$ are not comparable in $P$, then both $a\le b$ and $a \ge b$ must be witnessed by realizers.

There is a higher-order generalization of the dimension, defined as follows. Fix a parameter $r < |X|$. Then the $r$-dimension of $P$ is the minimum number of total orders that witness all legal ordering relationships among $r+1$-tuples of elements in $P$.

In response to comments: In particular, let $S$ be such a set of total orders. For any extension of the poset to a total order and any $r$-tuple of elements $R$, there must exist some total order in $S$ in which the set of elements in $R$ have the same ordering as in the extension.

For example, the trivial poset $\{a,b,c\}$ (no orderings) has dimension two via the two orderings $a,b,c$ and $c,b,a$. However, this poset has a 2-dimension of 6, because we need all the $3!=6$ orderings of the three elements.


  1. Is there any known geometric interpretation of the $r$-dimension like what we have for the dimension ?
  2. Are there known bounds on the $r$-dimension ? For example, we know that the dimension is upper bounded by the width (and this is a fairly weak bound in general).
share|cite|improve this question
From your informal definition and your example I am unable to extract a formal definition of $r$-dimension. Can you provide one? – user46855 Feb 16 '14 at 22:28
added formal definition. – Suresh Venkat Feb 17 '14 at 4:19

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.