FINITE DUALITIES, IN PARTICULAR IN FULL HOMOMORPHISMS

Abstract. This paper is a survey of several results concerning finite dualities, a special case of the famous Constraint Satisfaction Problem (CSP). In CSP, the point is to characterize a class C of objects X determined by constraints represented by the requirement of the existence of structure preserving mappings from X into special ones. In a finite duality, such a class C is characterized by the non-existence of special maps into X from a finite system of objects. In the first third of the article we recall some well-known facts concerning constraints represented by classical homomorphisms of relational systems. In the second part we present several results, not yet published but mostly already submitted, concerning the variant of full homomorphisms. The third part contains a few results on hypergraphs and complexes in this context. These form part of an investigation recently undertaken, and appear here first. In the Constraint Satisfaction Problem, one is concerned with objects X endowed with a given type of structure subjected to constraints, usually represented by a system of special objects B, in our case always finite, and the requirement that there exist a mapping X → B ∈ B suitably linked with the structures. (For a more precise formulation see Section 1 below.) One endeavours to find a characterization, as transparent as possible, of the resulting class. This can sometimes be done by requiring the nonexistence of special maps Ai → X from a finite list of objects A1,..., An, or by requiring the non-existence of subobjects isomorphic to any of the Ais. Then we speak of a finite duality