Skip to main content
10 of 13
added 93 characters in body
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

Update. We also have $15 \le f(6) \le 17$. 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. But $f(6)=14$ was ruled out by exhaustive search over all $1.34 \times 10^{12}$ 14-posets, using the C code "posets.c" by Brinkmann & McKay to list the posets, and some more C code to test for universality (about 16 cpu-days of computation; would have been impossible in Sage). Doing exhaustive search over 15- or 16-element posets does not seem promising — I hope there are better ways of proving lower bounds.

Another computational approach, which gives 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. 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]].

Picture of 6-universal 17-poset

(Again bad layout, sorry; check the listed cover relation for reference.) This was done with very simple SageMath code (below), certainly one could do much more searching with faster C code.

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

Update (12.1.2021). You can knock me over with a feather. I had the brute-force search for 6-universal 16-posets running at a low priority "just in case we are lucky". The full search 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]].

icture of 6-universal 16-poset

(The question of a 15-element 6-universal poset is still open. Unless someone has faster methods, it will be settled in about week from now by brute force.)

Jukka Kohonen
  • 4.2k
  • 2
  • 21
  • 49