Graph Homomorphisms and Universal Algebra (Course Math Ma 01)
Topics:
We will study the time complexity of finite domain constraint satisfaction problems (finite domain CSP) with a focus on finite directed graphs. Important notions introduced in the course are clones, polymorphims, primitive positive definablility, ...
Language:
The course is offered in English.
Schedule:
| Mi | Start: 13:00 | End: 14:30 | WIL/C104 |
| Fr | Start: 11:10 | End: 12:40 | WIL/C106 |
We will use the Manuel Bodirsky Notes. If you attend the course and want to recieve emails from me, then register in the Opal course or contact me under . Here is an open text document, where you can write anonymus feedback.
| Date | Summary |
|---|---|
| 14.10.26 | Introduction. We introduced basic notions for graphs and digraphs. And we defined the homomorphism order on digraphs. In the script Section 2.1 and beginning of Section 2.2. |
| 16.10.26 | We showed the the graph homomorphism order is a lattice, introduces CSPs and discussed the complexity classes P and NP. Sections 2.2 and 2.3 |
| 21.10.26 | We introduced NP-hardness and stated the CSP-dichotomy theorem. We introduced cores and showed that every digraph has a (up to isomorphism) unique core. Section 2.4 |
| 23.10.26 | Exercise Sheet 1 (found in Opal) |