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

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.)

share|improve this question
    
Neat question. I guess the logic tag is because it came up in your logic class? –  Pete L. Clark May 25 '10 at 13:58
    
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. –  Joel David Hamkins May 25 '10 at 14:09
    
Correction: my student's lower bound is $n\log(n)-n$. –  Joel David Hamkins May 25 '10 at 14:41

2 Answers 2

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)$ (that's captain obvious advice, yes). Since $\log F(n)$ behaves like $cn^2$ (the lower estimate, which we need, is proved as follows: 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}$ patial orders, each isomorphism class is counted at most $n!$ times). So, $N^n> \binom{N}{n}\geq F(n)$, taking logarithms we get $n\log N > cn^2$, so $N$ should grow at least exponentially.

share|improve this answer
1  
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? –  Joel David Hamkins May 25 '10 at 17:46
    
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. –  Fedor Petrov May 25 '10 at 20:13

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(nlog(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(nlog(n)) + O(1) = O(nlog(n))$ bits, which is a contradiction as there are too many partial orders on $n$ elements to be represented in only $O(nlog(n))$ bits.

share|improve this answer
    
It is not true that $P_n \geq 2^{n^2/4}$. Also, LaTeX knows \log. –  JBL May 25 '10 at 17:19
    
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. –  Travis Service May 25 '10 at 18:19
    
+1. Travis, thanks very much for the argument--your information-theoretic way of analyzing it appeals to me very much. –  Joel David Hamkins May 25 '10 at 18:49

Your Answer

 
discard

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

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