Constraint Satisfaction and Universal Algebra learning seminar

Tuesday, October 15, 2013 10:30 am - 10:30 am EDT (GMT -04:00)

Alex Wires, Department of Pure Mathematics, University of Waterloo

“A Smooth Proof of the Smooth Theorem”

Bang-Jensen and Hell conjectured in 1990 that CSP Dichotomy holds for finite digraphs with no sources or sinks. This was positively verified by Barto, Kozik, and Niven by showing that a finite smooth digraph of algebraic length one closed under a Taylor operation has a loop at some vertex. We shall understand an easier proof of this fact developed by Barto and Kozik using the theory of absorption in Taylor algebras.