Skip to main content
3 of 13
Partial answer changed to full answer of f(5), from new computation.
Jukka Kohonen
  • 4.2k
  • 2
  • 21
  • 49

(Edited from earlier partial answer, which gave $f(5) \ge 11$.)

We have $f(5) = 11$.

A short proof shows that $f(5) \ge 10$. To be 5-universal (i.e. universal for 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 can be in the 5-chain. Also it must contain 5 incomparable elements (only two of which could be in the two 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. 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 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$.

picture

(Beware of bad layout, vertex 9 is not covered by 8, but by 10.)

To go further to $f(6)$, this code is probably not practical, mainly because Poset() generates the posets pretty slowly. In SageMath 8.8, it seems >90% of our computation time is spent there, and not in testing for universality. The best road forward is probably to use the C program by Brinkmann & McKay to generate the candidate posets. It should be lightning fast compared to Posets(), so then the bottleneck probably moves to the universality check. The B&M program can be found as an attachment to an old enhancement request for faster poset generation in SageMath. (Also McKay says in a comment here that he can send the code.)

# Find an u-poset that contains all n-posets as induced posets.
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
Jukka Kohonen
  • 4.2k
  • 2
  • 21
  • 49