Classification of δ-Invariant Amalgamation Classes

Hrushovski's generalization of the Fraisse construction has provided a rich source of examples in model theory, model theoretic algebra and random graph theory. The construction assigns to a dimension function s and a class K of finite (finitely generated) models a countable 'generic' structure. We investigate here some of the simplest possible cases of this construction. The class K will be a class of finite graphs; the dimension, 6 (A), of a finite graph A will be the cardinality of A minus the number of edges of A. Finally and significantly we restrict to classes which are s-invariant. A class of finite graphs is s-invariant if membership of a graph in the class is determined (as specified below) by the dimension and cardinality of the graph, and dimension and cardinality of all its subgraphs. Note that a generic graph constructed as in Hrushovski's example of a new strongly minimal set does not arise from a s-invariant class. We show there are countably many s-invariant (strong) amalgamation classes of finite graphs which are closed under subgraph and describe the countable generic models for these classes. This analysis provides co-stable generic graphs with an array of saturation and model completeness properties which belies the similarity of their construction. In particular, we answer a question of Baizhanov (unpublished) and Baldwin [5] and show that this construction can yield an co-stable generic which is not saturated. Further, we exhibit some co-stable generic graphs that are not model complete. Most of the definitions and notation are carried over from [1] or from Baldwin and Shi [4]. The existence of this variety of examples for graphs with the simplest choice of dimension function shows the diversity of even the class of theories with trivial forking.