On polymorphism-homogeneous relational structures and their clones. (Q2257979)

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.