Universal algebra

Ross Willard, Department of Pure Mathematics, University of Waterloo

Graphs, posets, polymorphisms, and the Constraint Satisfaction Problem Dichotomy Conjecture"

To kick of this term's seminar, I will briefly present all the main themes at play in current work on the Constraint Satisfaction Problem Dichotomy Conjecture. The ingredients are (1) finite graphs, posets, and other more general finite structures; (2) colouring/homomorphism problems obtained from a finite structure; (3) "idempotent polymorphisms" of a finite struc-
ture; (4) identities involving idempotent polymorphisms forcing varying degrees of nontriviality (called "Maltsev conditions"); (5) the "primitive-positive-interpretability" relation between - finite structures. I will have identify each of the main Maltsev conditions relevant to CSP and some secondary ones, characterize each main Maltsev condition by a class of structures which it forbids to be pp-interpretable, and state the conjectures connecting each main Maltsev condition to a computational complexity class.

Note: this is a 90-minute seminar.