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 .
If you have any questions send me an Email, come to my office, or go see me in the studyroom (B122 on Thursdays from 15:00 to 18:00).
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 | We introduced Polymorphisms and did Exercise Sheet 1 (found in Opal). |
| 28.10.26 | We introduced the arc-consistency procedure and show that it solves the CSP of H iff the powerset graph of H has a homomorphism into H. We introduced tree also duality, preparing the next characterization of AC. Section 3.1 and beginning of Section 3.2 |
| 30.10.26 | We showed that CSP(H) is solved by AC iff H has tree duality iff H has totally symmetric polymorphisms of all arities. Sections 3.2 and 3.3. |
| 04.11.26 | We finished with arc consistency, introduced path- and k-consistency and almost finished proving that the CSP of any digraph H that has a majority polymorphism is solved by path consistency. Sections 4.1 and 4.2. |
| 06.11.26 | Exercise Sheet 2 |
| 11.11.26 | We finished the majority proof. We introduced Maltsev operations and characterized the core digraphs that do have a Maltsev polymorphism as those that are directed paths or disjoint unions of cycles. We startet with structures. Sections 4.4 and beginning of Chapter 5. |
| 13.11.26 | |
| 18.11.26 | Public Holiday |
| 20.11.26 | Exercise Sheet 3 |
| 25.11.26 | |
| 27.11.26 | |