The core of an omega-categorical structure
by
Manuel Bodirsky
Humboldt Universitaet zu Berlin

A finite relational structure is a core if all endomorphisms are automorphisms. The concept of a core is important for the algebraic approach to the complexity study of constraint satisfaction problems. For infinite structures, many different generalizations of the notion of a core are possible. For arbitrary structures these generalizations are mostly inequivalent, and they do not have the nice properties known for cores of finite structures. A countable structure is countably categorical if the automorphism group of the structure has only finitely many orbits of k-tuples, for each k. These structures are intensively studied in model theory and in the theory of infinite permutation groups. We present a generalization of the notion of a core to countably categorical structures that shares the important properties of the core of a finite structure: we prove that such a structure always has an endomorphism whose image is a core and unique up to isomorphism. Moreover, this core is again countably categorical. We discuss various consequences for the theory of constraint satisfaction with countably categorical templates.

Date received: May 7, 2004