18
$\begingroup$

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.

$\endgroup$
15
  • 1
    $\begingroup$ Is there a database of small posets? It looks like you could brute-force search sizes up to 11 if you had such a database. $\endgroup$ Oct 27 '20 at 21:17
  • 1
    $\begingroup$ This may be useful: Posets on up to 16 points. I haven't found a list of them yet. $\endgroup$
    – 6005
    Oct 30 '20 at 17:07
  • 3
    $\begingroup$ If someone wants to do some programming, I can provide posets. Up to 11 points I can give you a gzipped file of about 140 MB. 12 points takes 3.1 GB which is more than my web server has free at the moment, but I could provide the generator program in C (you will need the 'nauty' package to compile it). $\endgroup$ Jan 4 '21 at 11:01
  • 1
    $\begingroup$ @BrendanMcKay Can you please provide the 318 6-posets? $\endgroup$
    – RobPratt
    Jan 5 '21 at 20:39
  • 1
    $\begingroup$ OEIS Sequence now published! Thanks everyone for the effort here! $\endgroup$
    – 6005
    Jan 6 '21 at 2:45
18
$\begingroup$

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

A 5-universal 11-poset

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

A 6-universal 16-poset

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.

$\endgroup$
11
  • $\begingroup$ This is great! Thank you for the partial answer. $\endgroup$
    – 6005
    Jan 4 '21 at 4:55
  • $\begingroup$ I have proposed the sequence again, this time with f(5) = 11 at oeis.org/draft/A340318 $\endgroup$
    – 6005
    Jan 4 '21 at 17:21
  • 2
    $\begingroup$ If I understand correctly, here is another 5-universal poset on 11 elements, found via integer linear programming rather than explicit enumeration: $$(0, 1), (3, 2), (4, 5), (7, 6), (9, 5), (2, 1), (2, 10), (8, 5), (7, 4), (1, 8), (3, 9), (1, 6), (0, 4), (3, 7), (7, 8), (6, 5)$$ $\endgroup$
    – RobPratt
    Jan 5 '21 at 20:37
  • $\begingroup$ @RobPratt: Certainly there can be more than one n-universal poset of the minimum size, but is the one you present 5-universal? I think it lacks the induced 5-subposet with the cover relation {(0,1),(1,2),(2,3),(4,5)}, i.e. a 3-chain and a 2-chain which are incomparable to each other. At least I understood the original question as requiring induced subposets (= the subset inherits the order from the big poset), perhaps the original poster can clarify this point. $\endgroup$ Jan 5 '21 at 22:18
  • $\begingroup$ @JukkaKohonen The relation you listed uses 6 elements. $\endgroup$
    – RobPratt
    Jan 5 '21 at 22:34
7
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Nice ILP encoding. I wonder if it helps to hard-code some element mappings, e.g. decide beforehand that the elements of the $n$-chain $C_n = \{0,1,2,\ldots,n-1\}$ are mapped to the same numbers in the universal poset. This might break some symmetries in the solution space, and fix the values of several $x_{i,j}$. Or are ILP solvers nowadays clever enough to work such things out on their own? Come to think of it, one could also fix the image of an $n$-antichain. $\endgroup$ Jan 6 '21 at 19:21
  • 1
    $\begingroup$ Thanks. Yes, in fact, I had done a similar fixing for the antichain, as well as fixing $x_{i,j}=0$ for the corresponding pairs. Modern commercial solvers do exploit symmetry, but this can still help. $\endgroup$
    – RobPratt
    Jan 6 '21 at 19:36
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.