A004401 -id:A004401 - cp's OEIS frontend

A097911 Minimal order of a graph containing as induced subgraphs isomorphic copies of all graphs on n unlabeled nodes.

1, 3, 5, 8, 10, 14

Offset: 1

Dan Schwarz (dan_schwarz(AT)hotmail.com), Sep 04 2004

A graph that contains as induced subgraphs isomorphic copies of all graphs in a family F is called induced universal for F. - James Trimble, Nov 09 2021

16 <= a(7) <= 18 (Trimble, 2021). - James Trimble, Nov 09 2021

			a(3) = 5 as (P1 + K1)*K1 + K1 has 5 vertices and is easily seen minimal for 3. Here P1 is the path with one edge and K1 is an isolated vertex.

Noga Alon, Asymptotically optimal induced universal graphs, Geometric and Functional Analysis, 27(1):1-32, 2017.
Richard Rado, Universal graphs and universal functions, Acta Arith. 9 (1964), 331-340.
James Trimble, Induced universal graphs for families of small graphs, arXiv:2109.00075 [math.CO], 2021.
James Trimble, Partitioning algorithms for induced subgraph problems, Ph.D. Thesis, Univ. of Glasgow (Scotland, 2023), 134.

Cf. A034797, A004401

a(5)-a(6) added by James Trimble, Nov 09 2021

A348638 Minimal order of a graph containing as induced subgraphs isomorphic copies of all trees on n unlabeled nodes.

Original entry on oeis.org

1, 2, 3, 5, 7, 9, 11, 13

Offset: 1

James Trimble, Nov 09 2021

a(n) is the minimal order of an induced universal graph for the family of trees on n vertices.

a(9) <= 15 and a(10) <= 18 (Trimble, 2021).

James Trimble, Induced universal graphs for families of small graphs, arXiv:2109.00075 [math.CO], 2021.
James Trimble, Partitioning algorithms for induced subgraph problems, Ph.D. Thesis, Univ. of Glasgow (Scotland, 2023), 134.

Cf. A004401, A097911.

A212555 Values of ||G*(n)|| related to construction of graphs which contain all small trees.

Original entry on oeis.org

0, 1, 2, 4, 6, 8, 11, 14, 17, 21, 25

Offset: 0

N. J. A. Sloane, May 26 2012

Chung, F. R. K.; Graham, R. L. On graphs which contain all small trees. J. Combinatorial Theory Ser. B 24 (1978), no. 1, 14--23. MR0505812 (58 #21808a)

This is an upper bound on A004401.

Cf. A339573.

A380740 Number of smallest fully n-forested graphs.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 7, 13, 25, 17

Offset: 1

Eric W. Weisstein, Jan 31 2025

Eric Weisstein's World of Mathematics, Fully Forested Graph.

Cf. A004401 (edge counts of smallest fully forested graphs).

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

Original entry on oeis.org

0, 1, 3, 5, 8, 11, 16

Offset: 0

Caleb Stanford, Jan 04 2021

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.
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).
a(4) = 8 verified using a computer-assisted proof with a SAT solver.
a(5) = 11 proven on MathOverflow.
a(6) = 16 and 16 <= a(7) <= 25 proven on MathOverflow. - Jukka Kohonen, Jan 15 2021

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

Joel David Hamkins and Fedor Petrov, What is the minimal size of a partial order that is universal for all partial orders of size n?, MathOverflow.
Jukka Kohonen, What is the minimum size of a partial order containing all partial orders of size 5? (proofs of a(5)=11, a(6)=16 and 16 <= a(7) <= 25), MathOverflow.
Caleb Stanford, Alloy program to verify a(n) for small n, GitHub.

Cf. A000112, A001035, A004401, A097911.

# 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

a(6) from Jukka Kohonen, Jan 15 2021

cp's OEIS Frontend

A097911 Minimal order of a graph containing as induced subgraphs isomorphic copies of all graphs on n unlabeled nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A348638 Minimal order of a graph containing as induced subgraphs isomorphic copies of all trees on n unlabeled nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

A212555 Values of ||G*(n)|| related to construction of graphs which contain all small trees.

Views

Author

Keywords

Links

Crossrefs

A380740 Number of smallest fully n-forested graphs.

Views

Author

Keywords

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Sage

Extensions