Graph Homomorphisms and Universal Algebra
Lecture of the Module Math-Ma-DISMAT "Discrete Mathematics", summer semester 2020.
The language of the course is English.
Topics
The course is about the interplay between the theory of graph homomorphisms and universal algebra.
Target Audience
Master programs mathematics, techno mathematics, business mathematics, diploma students in computer science with mathematics minor (specialising in algebra).
Prerequisites
Competences of the bachelor studies, prior knowledge of the module Math Ba ALGSTR is desirable, but not strictly required.
Times (for the time after the pandemic restrictions)
Monday | 2. DS | WIL/C105/U |
Wednesday | 3. DS | BZW/A253/U |
Script
The English course notes can be downloaded here. Important note: not the videos, but the course notes are the definite material and define the course content. Please report all mistakes, typos, unclear places, etc to the author! Some sections at the end of the course notes will be added later.
Videos
There is public video material available:
- Session 1: Introduction
- Session 2: The Arc Consistency Procedure
- Session 3: Cores and Polymorphisms
- Excursion (does not belong to the course in the proper sense, covers background): Basics of Complexity Theory.
- Session 4: The Path Consistency Procedure and Majority Polymorphisms.
- Session 5: Digraphs with a Maltsev Polymorphism.
- Session 6: Relational Structures and Primitive Positive Definitions.
- Session 7: Primitive Positive Interpretations.
- Session 8: Clones.
- Session 9: Minimal Clones.
- Session 10: Schaefer's Theorem.
- Session 11: Pseudo-Varieties.
- Session 12: Birkhoff's theorem.
- Session 13: Siggers' theorem.
More videos will be uploaded each week during the semester.
Literature
The lecture is based on the course notes. For complementary literature we refer to the book `Graph Homomorphisms' of Jaroslav Nesetril and Pavol Hell (2004, Oxford University Press).
Exercises
Instructors: Manuel Bodirsky and Florian Starke.
- Series 1 Recommended minimum reading for the first week: Section 1.1 and 1.2.
- Series 2 Recommended minimum reading for the second week: until the end of Section 1.
- Series 3 Recommended minimum reading for the third week: Section 2.
- Series 4 Recommended minimum reading for week 4 and 5: Section 3.
- Series 5 Recommended minimum reading for week 6 and 7: Section 4.
- Series 6