Charles Explorer logo
🇬🇧

Dualities in full homomorphisms

Publication at Faculty of Mathematics and Physics |
2009

Abstract

The Constraint Satisfaction Problem (CSP) is studied for constraints given as requirements in full graph homomorphisms. It is proved that for every finite (full) system of constraints there exists a finite duality, that is, a finite system of prohibited sources, or subobjects, equivalent with the constraint task.

The converse, however does not hold, in fact it is, rather, rare - it is a phenomenon of the Ramsey type. As an illustration we present a number of concrete finite dualities, and of the associated Ramsey phenomena.