9
$\begingroup$

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).
$\endgroup$
2
  • $\begingroup$ From your informal definition and your example I am unable to extract a formal definition of $r$-dimension. Can you provide one? $\endgroup$
    – user46855
    Feb 16, 2014 at 22:28
  • $\begingroup$ added formal definition. $\endgroup$ Feb 17, 2014 at 4:19

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.