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.)
Best Answer
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}$.