Combinatorics

Topics

• Basics about graphs, e.g. about matchings and colorability,
• LP Duality and combinatorial applications
• The probabilistic method (for example for prorving the existence of graphs with high chromatic number and high girth),  random graphs
• Ramsey theory
• enumerative combinatorics and generating functions, analytic combinatorics.

There is a overview video about this course in youtube.  

Target audience

Bachelor-Studies mathematics (5. Sem.); Staatsexamen: Höheres Lehramt an Gymnasien (9. Sem., for the module "Mathematische Vertiefung"); for diploma computer science students with math minor ("Vertiefung im Nebenfach")

Subscription

Über  Opal.

Prerequisites

Competences from the Module Math-Ba-ALGZTH, Math-Ba-ANAG, Math-Ba-LAAG and Math-Ba-PROG.

For computer science students: the obligatory math courses for undergrad computer science students are sufficient. 

Time and place: 

In the winter semester 2021/21 there are still room capacity restrictions because of the Corona pandemic. However, we are optimistic that this course can be held physically in the rooms announced below. 

Further comments

The course instructor is Prof. Manuel Bodirsky. The language of the course is English on demand, otherwise in German. We recommend urgently to take notes in class. Active participation in the exercises is obligatory.

Literature

• Combinatorics: Topics, Techniques, Algorithms, by Peter J. Cameron, Cambridge University Press.
• Graph theory, by Reinhard Diestel, Springer Verlag, Heidelberg, 2010. Vierte Auflage.
• More to follow during the course.

Course Notes

English Course notes are provided. Nonetheless we recommend to take handwritten notes during class. 

Exercises

Part of the course are obligatory exercise sessions, approximately one out of 4 meetings. Homework will be assigned.