Graph Homomorphisms and Universal Algebra (Modul Math Ma 35)
Topics:
We will study the time complexity of finite domain constraint satisfaction problems (finite domain CSP) and the connections of the CSP to some universal algebraic notions such as clones, polymorphisms, varieties, equational theories, etc.
Language:
The course is offered in English.
Schedule:
| Mo | Start: 16:40 | End: 18:10 | WIL/A120 |
| Fr | Start: 11:10 | End: 12:40 | Z21/217 |
We will use the Manuel Bodirsky Notes
| Date | Summary |
| 07.04 | Intro lecture. We defined a CSP, a relational structure, homomorphism, finite domain CSP, CSP with restricted template, and polymorphism. Next time we will cover material from sections 2.1-2.4 of the Bodirsky notes. |
| 11.04 |
Defined homomorphism preorder and the partial order on equivalence classes. We showed this is a lattice order for digraphs. We also gave most of the basic definitions in 2.1 and 2.2. Homework problems: all 2.2 problems. |
| 14.04 |
More on the homomorphism order for graphs, infinite ascending, descending chains, antichains. Definition of core graph, we showed every homomorphic equivalence class of finite digraphs has a unique core which is isomorphic to an induced subgraph on each representative of the class. Homework problems: 17-23 |