May 3
Gregory Cherlin,
Rutgers University
Countable universal graphs with forbidden subgraphs
Abstract
Definition: A collection $\mathcal F$ of forbidden subgraphs is a Rado family if the class of countable $\mathcal F$-free graphs contains a universal structure with respect to embeddings as induced subgraphs. (By 'forbidden' I mean forbidden as subgraphs; usage varies in the literature.)
We consider the following decision problem for Rado families.
Problem: Given a finite set $\mathcal F$ of finite, connected graphs, determine whether or not it is a Rado family.
Question: Is this a decidable problem?
If we specialize to the sake of a single constraint then we speak instead of a Rado constraint. Much is known, and much more conjectured, about the case of a single constraint.
Conjecture: The decision problem for the case of a single constraint is decidable.
Discussion
From the model theoretic side, a finite collection of forbidden subgraphs specifies a universal theory with some special properties: notably, there is a model companion. When we restrict to families of connected constraints, the theory has joint embedding and the model companion is complete. In model theoretic terms the question becomes whether the model companion has a countable universal model with respect to elementary embedding, for which a purely type theoretic criterion is known.
Decision problems for other model theoretic properties of the model companion are natural. We have focused on this one because the question came to us from graph theory. However, even in that form, two variants are relevant.
- Can we decide whether the model companion is $\aleph_0$-categorical?
- Dropping the connectedness hypothesis on the constraints, can we decide whether the model companion is complete?
The main source of positive answers to the universality problem appears to be the $\aleph_0$-categorical case, and this has some theoretical justification. The most direct route to understanding the original graph theoretical problem appears to take the detour through $\aleph_0$-categoricity.
As time allows, I would like to discuss the following three points.
- What we know, and what we expect, in the case of a single constraint;
- Methods of proof (algebraic closure; induction by pruning);
- The status of the decision problem for j.e.p. and its analog in the theory of permutation pattern classes (work of Braunfeld).
This is joint work with Shelah, e.g. [Sh689].