cp's OEIS Frontend

A340318 Minimum size of a partial order that contains all partial orders of size n.

%I A340318 #28 Feb 19 2021 20:32:59
%S A340318 0,1,3,5,8,11,16
%N A340318 Minimum size of a partial order that contains all partial orders of size n.
%C A340318 a(n) is the minimum number of elements in a poset P such that every poset of size n is isomorphic to a subset of P, where the subset inherits the order from P.
%C A340318 Elementary bounds are a(n) >= 2n-1 because it must contain a chain and an antichain, and a(n) <= 2^n-1 because every partial order embeds into the powerset partial order on n elements. It is shown in the MathOverflow link that a(n) has no polynomial upper bound. This is in particular derived from binomial(a(n),n) >= A000112(n).
%C A340318 a(4) = 8 verified using a computer-assisted proof with a SAT solver.
%C A340318 a(5) = 11 proven on MathOverflow.
%C A340318 a(6) = 16 and 16 <= a(7) <= 25 proven on MathOverflow. - _Jukka Kohonen_, Jan 15 2021
%H A340318 Joel David Hamkins and Fedor Petrov, <a href="https://mathoverflow.net/questions/25874/what-is-the-minimal-size-of-a-partial-order-that-is-universal-for-all-partial-or">What is the minimal size of a partial order that is universal for all partial orders of size n?</a>, MathOverflow.
%H A340318 Jukka Kohonen, <a href="https://mathoverflow.net/a/380314/32499">What is the minimum size of a partial order containing all partial orders of size 5?</a> (proofs of a(5)=11, a(6)=16 and 16 <= a(7) <= 25), MathOverflow.
%H A340318 Caleb Stanford, <a href="https://github.com/cdstanford/curiosities/blob/master/universal-poset/universal-poset.als">Alloy program to verify a(n) for small n</a>, GitHub.
%e A340318 a(2) = 3 because there are 2 nonisomorphic posets on two elements, and both embed into the poset of three elements {a, b, c} with ordering a < b (and other pairs are incomparable).
%e A340318 a(3) = 5 because all posets on three elements can be embedded into {a, b, c, d, e} with ordering a < d, b < c < d, and b < e.
%o A340318 (Sage)
%o A340318 # Find an u-poset that contains all n-posets as induced posets.
%o A340318 def find_universal_poset(n,u):
%o A340318     PP = list(Posets(n))
%o A340318     for U in Posets(u):
%o A340318         ok = True
%o A340318         for P in PP:
%o A340318             if not U.has_isomorphic_subposet(P):
%o A340318                 ok = False
%o A340318                 break
%o A340318         if ok:
%o A340318             return U
%o A340318     return None
%Y A340318 Cf. A000112, A001035, A004401, A097911.
%K A340318 nonn,more
%O A340318 0,3
%A A340318 _Caleb Stanford_, Jan 04 2021
%E A340318 a(6) from _Jukka Kohonen_, Jan 15 2021