Return to Question

This earlier MO question asks to find the minimum size of a partial order that is universal for all partial orders of size $n$, i.e. any partial order of size $n$ embeds into it, preserving the order. In particular, the question asks if the minimum size $f(n)$ has a polynomial upper bound, to which the answer is no.

In this question, I am interested in some concrete values of $f(n)$ for small $n$. So far, I know that:

• $f(0) = 0$

• $f(1) = 1$

• $f(2) = 3$

• $f(3) = 5$

• $f(4) = 8$

• $f(n) \ge 2n - 1$

• $f(n) \in \Omega(n^k)$ for all $k$

Can we compute some additional values in this sequence? In particular, can we compute $f(5)$?

Notes

• I was able to verify $f(4) = 8$ using a computer-assisted proof using a SAT solver. I also tried naive enumeration of posets and checking for universality, but this fails at around $f(4)$. Computing $f(5)$ may require smarter enumeration, in particular better symmetry breaking.

• The sequence does not appear to be in OEIS yet (it does not appear to be any of the sequences beginning with 1, 3, 5, 8). I submitted this draft, and it was suggested that the sequence should be posted to MathOverflow to find more terms.

EDIT: New OEIS Draft with f(5) = 11 here.

This earlier MO question asks to find the minimum size of a partial order that is universal for all partial orders of size $n$, i.e. any partial order of size $n$ embeds into it, preserving the order. In particular, the question asks if the minimum size $f(n)$ has a polynomial upper bound, to which the answer is no.

In this question, I am interested in some concrete values of $f(n)$ for small $n$. So far, I know that:

• $f(0) = 0$

• $f(1) = 1$

• $f(2) = 3$

• $f(3) = 5$

• $f(4) = 8$

• $f(n) \ge 2n - 1$

• $f(n) \in \Omega(n^k)$ for all $k$

Can we compute some additional values in this sequence? In particular, can we compute $f(5)$?

Notes

• I was able to verify $f(4) = 8$ using a computer-assisted proof using a SAT solver. I also tried naive enumeration of posets and checking for universality, but this fails at around $f(4)$. Computing $f(5)$ may require smarter enumeration, in particular better symmetry breaking.

• The sequence does not appear to be in OEIS yet (it does not appear to be any of the sequences beginning with 1, 3, 5, 8). I submitted this draft, and it was suggested that the sequence should be posted to MathOverflow to find more terms.

EDIT: New OEIS entry with f(5) = 11 here.

This earlier MO question asks to find the minimum size of a partial order that is universal for all partial orders of size $n$, i.e. any partial order of size $n$ embeds into it, preserving the order. In particular, the question asks if the minimum size $f(n)$ has a polynomial upper bound, to which the answer is no.

In this question, I am interested in some concrete values of $f(n)$ for small $n$. So far, I know that:

• $f(0) = 0$

• $f(1) = 1$

• $f(2) = 3$

• $f(3) = 5$

• $f(4) = 8$

• $f(n) \ge 2n - 1$

• $f(n) \in \Omega(n^k)$ for all $k$

Can we compute some additional values in this sequence? In particular, can we compute $f(5)$?

Notes

• I was able to verify $f(4) = 8$ using a computer-assisted proof using a SAT solver. I also tried naive enumeration of posets and checking for universality, but this fails at around $f(4)$. Computing $f(5)$ may require smarter enumeration, in particular better symmetry breaking.

• The sequence does not appear to be in OEIS yet (it does not appear to be any of the sequences beginning with 1, 3, 5, 8). I submitted this draft, and it was suggested that the sequence should be posted to MathOverflow to find more terms.

This earlier MO question asks to find the minimum size of a partial order that is universal for all partial orders of size $n$, i.e. any partial order of size $n$ embeds into it, preserving the order. In particular, the question asks if the minimum size $f(n)$ has a polynomial upper bound, to which the answer is no.

In this question, I am interested in some concrete values of $f(n)$ for small $n$. So far, I know that:

• $f(0) = 0$

• $f(1) = 1$

• $f(2) = 3$

• $f(3) = 5$

• $f(4) = 8$

• $f(n) \ge 2n - 1$

• $f(n) \in \Omega(n^k)$ for all $k$

Can we compute some additional values in this sequence? In particular, can we compute $f(5)$?

Notes

• I was able to verify $f(4) = 8$ using a computer-assisted proof using a SAT solver. I also tried naive enumeration of posets and checking for universality, but this fails at around $f(4)$. Computing $f(5)$ may require smarter enumeration, in particular better symmetry breaking.

• The sequence does not appear to be in OEIS yet (it does not appear to be any of the sequences beginning with 1, 3, 5, 8). I submitted this draft, and it was suggested that the sequence should be posted to MathOverflow to find more terms.

EDIT: New OEIS Draft with f(5) = 11 here.