The universality problem for C-free graphs
Let be a finite set of finite graphs. A graph is -free if it contains no subgraph isomorphic to any member of ; the forbidden subgraph need not be induced. A strong embedding is an injective map preserving both adjacency and nonadjacency, so its image is an induced subgraph of . The universality question asks which admit a countable -free graph such that every countable -free graph strongly embeds into ; equivalently, for which does
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
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.