Cores of Countably Categorical Structures

Abstract

A relational structure is a core, if all its endomorphisms are embeddings. This notion is important for computational complexity classification of constraint satisfaction problems. It is a fundamental fact that every finite structure has a core, i.e., has an endomorphism such that the structure induced by its image is a core; moreover, the core is unique up to isomorphism. Weprove that every ω-categorical structure has a core. Moreover, every ω-categorical structure is homomorphically equivalent to a model-complete core, which is unique up to isomorphism, and which is finite or ω-categorical. We discuss consequences for constraint satisfaction with ω-categorical templates.

Cited by in corpus (6)

• Projective clone homomorphisms
• Towards a Ryll-Nardzewski-type Theorem for weakly oligomorphic structures
• ω-categorical structures avoiding height 1 identities
• Distance Constraint Satisfaction Problems
• Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems)
• On a stronger reconstruction notion for monoids and clones