Graph Homomorphisms and Universal Algebra

Lecture of the Module Math-Ma-DISMAT "Discrete Mathematics", summer semester 2023.
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

Course Notes

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.

Subscription

If you are interested in participating at the course, please let me know by email and additionally subscribe on Opal.

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. 

Literature

The lecture is based on the course notes. References to text-books will be given in class. 

Exercises

TBA