On polymorphism-homogeneous relational structures and their clones.

Galois connections homomorphism-homogeneity polymorphism clones polymorphism-homogeneity quantifier elimination relational structures weak oligomorphy

Mathematics Subject Classification ID

Quantifier elimination, model completeness, and related topics (03C10) Interpolation, preservation, definability (03C40) Infinite graphs (05C63) Partial orders, general (06A06) Relational systems, laws of composition (08A02) Structure theory of algebraic structures (08A05) Automorphisms and endomorphisms of algebraic structures (08A35)

Abstract: A relational structure is homomorphism-homogeneous if every homomorphism between finite substructures extends to an endomorphism of the structure. This notion was introduced recently by Cameron and Nev{s}etv{r}il. In this paper we consider a strengthening of homomorphism-homogeneity --- we call a relational structure polymorphism-homogeneous if every partial polymorphism with a finite domain extends to a global polymorphism of the structure. It turns out that this notion (under various names and in completely different contexts) has been existing in algebraic literature for at least 30 years. Motivated by this observation, we dedicate this paper to the topic of polymorphism-homogeneous structures. We study polymorphism-homogeneity from a model-theoretic, an algebraic, and a combinatorial point of view. E.g., we study structures that have quantifier elimination for positive primitive formulae, and show that this notion is equivalent to polymorphism-homogeneity for weakly oligomorphic structures. We demonstrate how the Baker-Pixley theorem can be used to show that polymorphism-homogeneity is a decidable property for finite relational structures. Eventually, we completely characterize the countable polymorphism-homogeneous graphs, the polymorphism-homogeneous posets of arbitrary size, and the countable polymorphism-homogeneous strict posets.

Review text

A relational structure is homomorphism-homogeneous if every homomorphism between finite substructures extends to an endomorphism of the structure. In the paper the following strengthening of homomorphism-homogeneity is considered: a relational structure is called polymorphism-homogeneous if every partial polymorphism with a finite domain can be extended to a global polymorphism of the structure. Polymorphism-homogeneity is studied from a model-theoretic, an algebraic, and a combinatorial point of view. Among others, structures that have quantifier elimination for primitive positive formulas are shown to be equivalent with polymorphism-homogeneity for weakly oligomorphic structures. It is demonstrated how Baker-Pixley theorem can be used to show that polymorphism-homogeneity is a decidable property for finite relational structures. The countable polymorphism-homogeneous graphs, the polymorphism-homogeneous posets of arbitrary size, and the countable polymorphism-homogeneous strict posets are completely characterized.

Recommendations

Cites work

Cited in

(19)

This page was built for publication: On polymorphism-homogeneous relational structures and their clones.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2257979)