KAIST Discrete Math Seminar

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.