What is the minimal size of a partial order that is universal for all partial orders of size n?

Question

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

Answer 1

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}$.

Answer 2

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 !

Answer 3

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.