Pure Math and C&O Joint ColloquiumExport this event to calendar

Wednesday, April 3, 2019 — 4:30 PM EDT

Ben Moore, University of Waterloo

"A proof of the Hell-Neˇsetˇril Dichotomy via Siggers Polymorphism"

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ˇsetˇril 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.

MC 4020

S M T W T F S
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
  1. 2019 (182)
    1. November (16)
    2. October (19)
    3. September (13)
    4. August (7)
    5. July (12)
    6. June (18)
    7. May (22)
    8. April (11)
    9. March (25)
    10. February (17)
    11. January (22)
  2. 2018 (219)
    1. December (2)
    2. November (32)
    3. October (27)
    4. September (26)
    5. August (4)
    6. July (9)
    7. June (13)
    8. May (17)
    9. April (13)
    10. March (28)
    11. February (27)
    12. January (21)
  3. 2017 (281)
  4. 2016 (335)
  5. 2015 (209)
  6. 2014 (235)
  7. 2013 (251)
  8. 2012 (135)