The universality problem for C-free graphs

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

All graphs are simple and undirected. Let $\mathcal C$ be a finite set of finite graphs. A graph $G$ is $\mathcal C$-free if no subgraph of $G$ is isomorphic to a member of $\mathcal C$; the excluded subgraphs need not be induced. Write $\mathcal G_{\mathcal C}$ for the class of all countable $\mathcal C$-free graphs. A strong embedding $e:H\to G$ is an injective map on vertices such that two vertices of $H$ are adjacent if and only if their images are adjacent in $G$. A universal member $U\in\mathcal G_{\mathcal C}$ must admit a strong embedding of every $H\in\mathcal G_{\mathcal C}$.

Statement recorded in the supplied source.

Characterize all finite sets $\mathcal C$ of finite graphs for which $\mathcal G_{\mathcal C}$ has a universal member under strong embeddings. [S2]

Short English statement

Which finite lists of forbidden finite subgraphs permit a countable graph containing every countable graph avoiding that list as an induced subgraph?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 7600011 (AMR-075-0011). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Gregory Cherlin, Saharon Shelah and Niandong Shi, Universal Graphs with Forbidden Subgraphs and Algebraic Closure, arXiv:math/9809202v1 (15 September 1998), General Theory and Section 1, Definition 1, p. 3; Introduction, pp. 1--2. https://arxiv.org/pdf/math/9809202.