skip to content

Constraint satisfaction problems and dualities

Monday 6th March 2006 - 11:00 to 12:00
INI Seminar Room 1

We consider constraint satisfaction (or homomorphism) problems of the form CSP(B): given a structure A, is there a homomorphism from A to a fixed structure B? The concept of duality for CSPs is based on the idea of providing an obstruction set (of structures) for homomorphism to B. There exist several types of duality according to the properties of obstruction sets. In this talk, we will review three main types of duality and discuss the problem of characterising structures with a given type of duality.

University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons