Tree Dualities for Constraint Satisfaction

摘要

For a fixed relational vocabulary r and a fixed finite r-structure B, the constraint satisfaction problem for B, denoted CSP(B), is to decide whether there is a homomorphism from a given finite r-structure A to B (A → B, in symbols). The study of such problems has recently been a very active research area. One attractive feature of this line of research is that it uses, and often combines, many different mathematical approaches (e.g. combinatorics, logic, algebra). This feature is clearly seen in the study of CSP dualities (see survey [2]), where the non-existence of a homomorphism to B is explained by the presence of a "nice enough" obstruction. An excellent example of combining approaches is provided by the following theorem [6,5], which is classical in the area. In my talk, I will discuss the above mentioned approaches and some recent results, including [1,3,4], where conditions 1-6 of Theorem 1 are strengthened or relaxed.