← All problems

The universality problem for C-free graphs

24 years old · documented by

Let C\mathcal C be a finite set of finite graphs. A graph GG is C\mathcal C-free if it contains no subgraph isomorphic to any member of C\mathcal C; the forbidden subgraph need not be induced. A strong embedding f:H↪Gf:H\hookrightarrow G is an injective map preserving both adjacency and nonadjacency, so its image is an induced subgraph of GG. The universality question asks which C\mathcal C admit a countable C\mathcal C-free graph GG such that every countable C\mathcal C-free graph strongly embeds into GG; equivalently, for which C\mathcal C does

∃G  [G is countable and C-free, and ∀H (H countable and C-free⇒H embeds as an induced subgraph of G)]\exists G\;\bigl[G\text{ is countable and }\mathcal C\text{-free, and }\forall H\,(H\text{ countable and }\mathcal C\text{-free}\Rightarrow H\text{ embeds as an induced subgraph of }G)\bigr]

hold? The principal classification results below concern finite sets of finite connected constraints, and many concern a single constraint. Cherlin and Shelah (August 2014) Cherlin and Tallgren (2013)

Background

The systematic study of countable universal graphs avoiding prescribed finite subgraphs goes back to Rado. The problem is sensitive to the meaning of “universal”: weak universality asks for embeddings as ordinary subgraphs, whereas strong universality requires induced embeddings. The literature therefore often first studies weak universality, even when the desired conclusion is strong. One useful model-theoretic connection is the algebraic-closure operator associated with a constraint: for finite sets of finite connected constraints, local finiteness of this operator is sufficient for a countable universal graph. It is not necessary in general, so this criterion does not by itself classify the constraints. Cherlin and Shelah (August 2014) Cherlin and Tallgren (2013)

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.