Perlen der Kombinatorik

Prof. Peter Bürgisser, WS02/03

Termine

Vorlesung (V3)
Di  13:15 - 15:45    A3            P. Bürgisser

Übung (Ü2)
Mo  11:15 - 12.45    E2.304        M. Ziegler

Scheinerwerb
50% der Punkte in den Übungen

 
 

Inhalt der Vorlesung

Die Kombinatorik hat den Reiz direkter Fragestellungen, die oft mit originellen Ideen ohne grossen technischen Aufwand erfolgreich behandelt werden können. Das Ziel der Veranstaltung ist der gemeinsame Genuss einer Reihe solcher Rosinen oder Perlen der Kombinatorik. Das kürzlich erschienene "BUCH der Beweise" von M.Aigner und G.Ziegler hat eine ähnliche Zielsetzung und sei wärmstens empfohlen. Ich werde mich teilweise auf Vorlesungen stützen, die ich bei V.Strassen gehört habe, und die sich ihrerseits stark an das schöne Buch von K.Jacobs anlehnen.  
 

Vorläufige Übersicht

  1. Heiratssatz und seine Verwandten
    1. Heiratssatz
    2. Partiell geordnete Mengen
    3. Möbius Funktionen
  2. Flüsse und Zusammenhang
    1. Fluß-Schnitt Theorem
    2. Anwendungen auf Paarungen
    3. Zusammenhang
    4. Superkonzentratoren
  3. Färbungen
    1. Knotenfärbungen
    2. Färben ebener Graphen
    3. Färben von Graphen auf Flächen
  4. Extremalprobleme
    1. Ramsey-Theorie
    2. Vermeidung von Teilgraphen
    3. Szemeredis Regularitätslemma
  5. Zufallsgraphen
    1. Probabilistische Methode
    2. Eigenschaften fast aller Graphen
    3. Schwellenfunktionen und Varianz

Die Veranstaltung wird im SS03 fortgesetzt mit einem Seminar.  
 

Literaturangaben

Einige dieser Bücher sind im Semesterapparat #26 der Bibliothek verfügbar.  
 

Übungsaufgaben

Abgabe jeweils Montags bis 11:00h im D3-Flur: rechter Kasten, das Fach ganz rechts in der Mitte (x=8,y=3)


M. Ziegler