(Edited several times from earlier partial answer, which gave $f(5) \ge 11$.)
We have exact results $f(5) = 11$ and $f(6)=16$, and bounds $16 \le f(7) \le 25$.
## 1. Proving $f(5)=11$ ##
A short proof shows that $f(5) \ge 10$. To be 5-universal (*i.e.* contain isomorphic copies of all partial orders of 5 elements), our poset must contain a 5-chain. Also it must contain two incomparable 2-chains, only one of which could overlap the 5-chain. Also it must contain 5 incomparable elements (only two of which could be in the previous chains). So at least 5+2+1+1+1 = 10 elements. I believe this is essentially the kind of lower-bound argument that was mentioned in the [earlier question][1]. This "multiple chains" argument says nothing about branching structures in the 5-posets, so perhaps one could consider them and work out an improved lower bound.
A really brute-force SageMath code (see below) tries all 10-posets (about 2.6 million) in about 15 hours, and finds no 5-universal posets, so this proves $f(5) \ge 11$.
Although the code is pretty slow, luckily with 11-posets it finds a solution in just 22 hours, having tried 1.0% of all approx. [47 million][2] 11-posets. The 11-poset with cover relation
[[0, 1], [0, 2], [1, 4], [1, 9], [2, 5], [2, 7], [2, 8],
[3, 4], [3, 5], [3, 6], [4, 7], [4, 8], [5, 10], [7, 10],
[8, 10], [9, 10]]
is 5-universal so we have $f(5) \le 11$.
[![A 5-universal 11-poset][3]][3]
# Find a u-poset that contains all n-posets as induced subposets.
def find_universal_poset(n,u):
PP = list(Posets(n))
for U in Posets(u):
ok = True
for P in PP:
if not U.has_isomorphic_subposet(P):
ok = False
break
if ok:
return U
return None
## 2. Proving $f(6)=16$ ##
For $f(6)$ the SageMath code is too slow. We can do faster brute-force in two phases: (1) list the candidate posets using "posets.c" by Brinkmann & McKay, available in an old SageMath [enhancement request][4], and (2) check them for 6-universality by C code corresponding to the SageMath code listed above.
The multiple-chains argument gives easily $f(6) \ge 14$, because a 6-universal poset must contain a 6-chain, two mutually incomparable 3-chains, three such 2-chains, and six incomparable elements; these can overlap but at least 6+3+2+1+1+1=14 elements are required.
I have ruled out $f(6)=14$ by exhaustive search over all $1.34 \times 10^{12}$ 14-posets (about 16 cpu-days of computation), and ruled out $f(6)=15$ similarly (about 1200 cpu-days). The result rests on heavy computation, so it would be nice to have a more succint lower bound proof, perhaps from a more elaborate version of the multiple-chains argument.
Exhaustive search over all 16-posets would take about 500 cpu-years, but some solutions were found after just 190 cpu-hours, that is, having done about 1/20000 of the search space. (There must be quite a lot of 6-universal 16-posets out there, to explain this luck.) One of the solutions has cover relation
[[2, 0], [2, 1], [3, 0], [3, 1], [4, 0], [4, 1], [5, 0], [5, 1], [6, 0], [7, 0], [8, 2], [8, 3], [8, 4], [8, 6], [8, 7], [9, 6], [9, 7], [10, 6], [11, 9], [11, 10], [12, 2], [12, 3], [12, 10], [13, 9], [13, 12], [14, 5], [14, 7], [14, 12], [15, 11], [15, 13], [15, 14]].
So we have $f(6) = 16$.
[![A 6-universal 16-poset][5]][5]
Another computational approach for upper bounds is to start from a known 6-universal poset, such as the Boolean lattice $B_6$ (= power set with inclusion relation), and *remove elements one by one*, if possible without breaking the universality. The idea of removing some unneeded elements is already implicit in the [old question][1]. This is potentially much faster than brute-force for finding positive examples -- if they exist! Not knowing any better, I removed elements in random order until impossible, and restarted 100 times. Already here I got **one 17-poset** and seventeen 18-posets. This 6-universal 17-poset has cover relation
[[0, 11], [0, 13], [0, 15], [1, 2], [1, 3], [1, 5], [2, 8], [2, 11], [3, 11], [3, 12], [4, 5], [4, 10], [5, 6], [5, 7], [6, 9], [6, 11], [6, 14], [7, 8], [7, 12], [8, 9], [8, 13], [9, 16], [10, 11], [10, 12], [10, 15], [11, 16], [12, 13], [12, 14], [13, 16], [14, 16], [15, 16]].
def is_universal_poset(n, U):
return all(U.has_isomorphic_subposet(P) for P in Posets(n))
def reduce_universal(n, P):
print(P)
if not is_universal_poset(n, P):
return None # Already nonuniversal
R = list(Permutations(P).random_element())
for r in R:
Pr = P.subposet(set(P).difference(set([r])))
if is_universal_poset(n, Pr):
return reduce_universal(n, Pr) # Try removing more
return P # Could not remove any element
## 3. Bounds for $f(7)$ ##
Brute-force is pretty much out of question (AFAIK nobody has listed all nonisomorphic 17-posets). For some loose bounds:
The multiple-chains argument gives $f(7) \ge 16$, because you need one 7-chain, two 3-chains, three 2-chains and seven incomparable elements, 7+3+2+1+1+1+1=16.
Removing random elements from $B_7$, we find easily (in less than ten random restarts) an example of a 7-universal 25-poset, with cover relation
[[0, 7], [0, 8], [0, 14], [1, 2], [1, 5], [2,
6], [2, 11], [3, 4], [3, 5], [3, 8], [3, 14], [4, 7], [4, 18], [5, 6],
[5, 7], [5, 12], [6, 9], [6, 13], [6, 19], [7, 22], [7, 23], [8, 9],
[9, 15], [9, 23], [10, 11], [10, 12], [10, 14], [11, 13], [11, 15],
[11, 20], [12, 13], [12, 15], [12, 16], [12, 20], [13, 21], [14, 15],
[14, 16], [15, 22], [16, 24], [17, 18], [18, 19], [19, 20], [19, 23],
[20, 21], [20, 22], [21, 24], [22, 24], [23, 24]].
So we have $f(7) \le 25$. This might be improved by trying more random restarts, perhaps with faster C code. I'm not planning to do that now, but it should be straightforward.
[1]: https://mathoverflow.net/questions/25874/what-is-the-minimal-size-of-a-partial-order-that-is-universal-for-all-partial-or
[2]: https://oeis.org/A000112/list
[3]: https://i.sstatic.net/83YUA.png
[4]: https://trac.sagemath.org/ticket/14110
[5]: https://i.sstatic.net/8plUE.png