Mark H. Siggers, CSP Dichotomy and the Fibre Construction

CSP Dichotomy and the Fibre Construction
Mark H. Siggers
Department of Mathematics, Kyungpook National University, Daegu, Korea
2009/04/10 Friday 4PM-5PM (Room 2411)
In recent years Constraint Satisfaction Problems (CSPs) have gained popularity among graph theorists due to the fact that they can be viewed as a generalisation of graph homomorphism problems. An important conjecture in the field is the CSP Dichotomy Classification Conjecture. Much of the recent progress towards a solution to this conjecture has come from the field universal algebra, and the statement of the Classification Conjecture requires a fair bit of algebraic language.

We talk about a recent graph theoretic construction, called the fibre construction, which can be used to get some of the important results achieved with universal algebra. This construction provides combinatorial version of the Classification Conjecture, and allows one to easily address restricted versions of the Conjecture. Further it leads to results unexpected by the universal algebra community.

Much of the material covered is joint work with Jaroslav Nešetřil and László Zádori.


Comments are closed.