What is the minimum size of a partial order containing all partial orders of size 5?

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 entry with f(5) = 11 here.

Answer 1

(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. 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$.

# 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, 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$.

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. 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.

Answer 2

You can solve the problem via integer linear programming as follows. Let $P$ be the set of $n$-posets to be covered, and for $(i,j)\in [n] \times [n]$ let $a_{p,i,j}$ indicate whether $i \preceq j$ in poset $p$. We want to find a universal $m$-set if possible. For $(i,j)\in [m] \times [m]$, let binary decision variable $x_{i,j}$ indicate whether $i \preceq j$ in the universal poset. For $p \in P$, $i_1\in [n]$, and $i_2\in [m]$, let binary decision variable $y_{p,i_1,i_2}$ indicate whether element $i_1$ in poset $p$ is assigned to element $i_2$ in the universal set. A universal $m$-poset exists if and only if the following constraints can be satisfied: \begin{align} \sum_{i_2 \in [m]} y_{p,i_1,i_2} &= 1 &&\text{for $p\in P$ and $i_1 \in [n]$} \tag1 \\ \sum_{i_1 \in [n]} y_{p,i_1,i_2} &\le 1 &&\text{for $p \in P$ and $i_2 \in [m]$} \tag2 \\ y_{p,i_1,i_2} + y_{p,j_1,j_2} - 1 &\le x_{i_2,j_2} &&\text{for $p\in P, (i_1,j_1) \in [n] \times [n], (i_2, j_2) \in [m] \times [m]$ with $a_{p,i_1,j_1}=1$} \tag3 \\ y_{p,i_1,i_2} + y_{p,j_1,j_2} - 1 &\le 1 - x_{i_2,j_2} &&\text{for $p\in P, (i_1,j_1) \in [n] \times [n], (i_2, j_2) \in [m] \times [m]$ with $a_{p,i_1,j_1}=0$} \tag4 \\ x_{i,j} + x_{j,k} - 1 &\le x_{i,k} &&\text{for $i,j,k \in [m]$} \tag5 \\ \\ \end{align} Constraint $(1)$ assigns each element in poset $p$ to exactly one element in the universal poset. Constraint $(2)$ assigns at most one element in poset $p$ to each element in the universal poset. Constraint $(3)$ enforces $$(y_{p,i_1,i_2} \land y_{p,j_1,j_2} \land a_{p,i_1,j_1}) \implies x_{i_2,j_2}.$$ Constraint $(4)$ enforces $$(y_{p,i_1,i_2} \land y_{p,j_1,j_2} \land \lnot a_{p,i_1,j_1}) \implies \lnot x_{i_2,j_2}.$$ Constraint $(5)$ enforces transitivity in the universal poset.

Answer 3

I will try to revive Sagemath's ticket #14110 and provide a Sagemath package for this enumeration (in fact, the C code, corresponding to the paper B. D. McKay and G. Brinkmann, Posets on up to 16 points, Order, 19 (2002) 147-179 - (mostly) due to Gunnar Brinkmann, which is using Brendan's McKay's nauty, is posted there.