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

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.

Question:

  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|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 at 22:28
    
added formal definition. –  Suresh Venkat Feb 17 at 4:19
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

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.