41
$\begingroup$

A partial order $\mathbb{B}$ is universal for a class $\cal{P}$ of partial orders if every order in $\cal{P}$ embeds order-preservingly into $\mathbb{B}$.

For example, every partial order $\langle\mathbb{P},\lt\rangle$ maps order-preservingly into its power set by the map $$p\mapsto\{q\in\mathbb{P}\mid q\leq p\}$$ that sends each element $p$ to its lower cone.

Thus, the power set order $\langle P(\{1,2,\ldots,n\}),{\subseteq}\rangle$ is universal for the class of partial orders of size $n$. This provides an order of size $2^n$ that is universal for orders of size $n$.

Question. What is the minimal size of a partial order that is universal for orders of size $n$?

In particular, is there a polynomial upper bound?

One can make at least slight improvements to the $2^n$ upper bound, by observing that the emptyset was not needed, as it never arises as a lower cone, and we don't need all the atoms, since if they are needed, then one can use the co-atoms instead. I suspect that there is a lot of waste in the power set order, but the best upper bound I know is still exponential.

For a lower bound, my current knowledge is weak and far from exponential. Any order that is universal for orders of size $n$ will contain a chain and an antichain, making it have size at least $2n-1$. (That bound is exact for $n\leq 3$.) A student in my intro logic course extended this to $n\log(n)$ by considering $k$ chains (and antichains) of size $n/k$.

Can one find better lower bounds?

Interestingly, the same student observed that we cannot in general expect to find unique smallest universal orders, since he found several orders of size 5 that are universal for orders of size 3 and which are minimal with that property. So in general, we cannot expect a unique optimal universal order. Does this phenomenon occur for every $n$? (He also found minimal universal orders of size larger than the minimal size universal order.)

$\endgroup$
3
  • $\begingroup$ Neat question. I guess the logic tag is because it came up in your logic class? $\endgroup$ May 25, 2010 at 13:58
  • $\begingroup$ The concept of universal structures is important in model theory and used in set theory (although usually for infinite structures). Also, the easiest way to show that every countable partial order embeds into the Turing degrees is to consider orders that are universal for countable orders (and there are countable such orders). For the warm-up to that theorem, we first embedded the finite powersets into the Turing degrees, and then concluded that all finite orders embed by universality. $\endgroup$ May 25, 2010 at 14:09
  • $\begingroup$ Correction: my student's lower bound is $n\log(n)-n$. $\endgroup$ May 25, 2010 at 14:41

3 Answers 3

27
$\begingroup$

Denote by $F(n)$ the number of different partial orders on the set of cardinality $n$. Then the minimal size $N$ of a partial order that is universal for orders of size $n$ satisfies $\binom{N}{n}\geq F(n)$. We may bound $F(n)$ from below as follows (for simplicity I assume that $n$ is even): take $n/2$ blue elements and $n/2$ red elements, then decide for each pair of red and blue elements $r_i$, $b_j$, whether $r_i > b_j$ or not. We get $2^{n^2/4}$ partial orders, and each isomorphism class is counted at most $n!$ times. So, $N^n/n!> \binom{N}{n}\geqslant F(n)\geqslant 2^{n^2/4}/n!$, thus $N>2^{n/4}$.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks very much for this excellent answer! I appreciate it very much. Could I ask kindly whether you might carry your argument through to the conclusion of an explicit lower bound? $\endgroup$ May 25, 2010 at 17:46
  • 2
    $\begingroup$ Of course, but if you carry on the sharp constant in the exponent, I have to think bit more:) Now the lower estimate is $2^{n/4+o(n)}$ . But I suppose that calculating the best constant is very hard, similar to Ramsey numbers precise asymptotics. $\endgroup$ May 25, 2010 at 20:13
6
$\begingroup$

We proved in this paper https://arxiv.org/abs/2012.01764 that the answer is $2^{n/4+o(n)}$. As observed in the other answers, a counting argument shows that this is optimal (up to the lower order term).

Update: May 7, 2021. Unfortunately there was a flaw in our proof and we have to take back this answer. The main result of the paper is still valid but we cannot obtain the universal poset as a direct consequence of our comparability labelling scheme for posets.

Very sorry, feel free to down-vote this answer !

$\endgroup$
6
$\begingroup$

There does not exist a polynomial upper bound.

Let $P_n$ be the number of partial orders on $n$ elements. It is know that $P_n \geq 2^{n^2/4}$. Thus, any method of uniquely representing the partial orders on $n$ elements, say in binary, will require at least $\log_2(2^{n^2/4}) = O(n^2)$ bits.

Now assume that for every $n$ there is a partial order on $n^k$, or fewer, elements, where $k$ is a constant, that is universal for the class of partial orders on $n$ elements. Fix some canonical ordering of the partial orders and let $U(n)$ be the first universal partial orders on $n^k$, or fewer elements.

Label each of the elements in $U(n)$ with a unique number from $1$ up to $\log_2(f(n)) = O(\log n)$ in some fixed canonical way. Now each partial order on $n$ elements can be uniquely described by writing down for each element that elements corresponding label in $U(n)$. This takes $O(n\log n)$ bits. However; this representation is not quite complete, as it seems to require the description of $U(n)$ to actually reconstruct a partial order given its representation in this form.

However, since $U(n)$ is the first universal partial order on $n^k$ or fewer elements, rather than appending an encoding of $U(n)$ to each partial order directly we can instead append an encoding of the following Turing machine $M$. $M$ takes in three arguments $n$, $i$ and $j$ and accepts if element $i$ is less than element $j$ in $U(n)$ and rejects otherwise. Given such a Turing machine we can clearly reconstruct the partial order. $M$ simply enumerates all partial orders of size between $n$ and $n^k$ and stops at the first partial order that is universal for all partial orders on $n$ elements. It then labels the elements of $U(n)$ in the canonical manner and accepts if the element labeled $i$ in $U(n)$ is less than the element labeled $j$ in $U(n)$. This TM has constant size.

We can thus uniquely and completely represent all partial orders on $n$ elements by $O(n\log n) + O(1) = O(n\log n)$ bits, which is a contradiction as there are too many partial orders on $n$ elements to be represented in only $O(n\log n)$ bits.

$\endgroup$
3
  • 2
    $\begingroup$ It is not true that $P_n \geq 2^{n^2/4}$. Also, LaTeX knows \log. $\endgroup$
    – JBL
    May 25, 2010 at 17:19
  • $\begingroup$ If you consider distinguishable elements then it is true that $P_n \geq 2^{n^2/4}$. If you consider indistinguishable elements then the there are still at least $\frac{2^{n^2/4}}{n!} \geq 2^{n^2/4 - n\log{n}} = 2^{\Theta(n^2)}$ partial orders on $n$ elements and the proof still holds. $\endgroup$ May 25, 2010 at 18:19
  • $\begingroup$ +1. Travis, thanks very much for the argument--your information-theoretic way of analyzing it appeals to me very much. $\endgroup$ May 25, 2010 at 18:49

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.