Wednesday, April 3, 2019 4:30 pm
-
4:30 pm
EDT (GMT -04:00)
Title: A proof of the Hell-Nešetřil Dichotomy via Siggers Polymorphisms
| Speaker: | Ben Moore |
| Affiliation: | University of Waterloo |
| Room: | MC 4020 |
Abstract:
In 2017, the constraint satisfaction dichotomy was proven via techniques from universal algebra. If we restrict this theorem to graphs, we get the Hell-Nešetřil Dichotomy, which is a statement about colouring graphs. It says that for a fixed graph H, determining if a graph G admits an H-colouring is NP-complete if and only if H does not contain a loop, and H is not bipartite. The original proof is graph theoretic, but I'll present a proof using more algebraic techniques due to Mark Siggers which should be accessible to everyone.