Dieses Seminar schliesst an die Vorlesung Perlen der Kombinatorik an. Ein Schwerpunkt ist die Erarbeitung verfeinerter diskreter probabilistischer Techniken (Konzentration, schwache Abhängigkeit). Diese haben zahlreiche Anwendungen in der diskreten Mathematik und theoretischen Informatik gefunden (Zufallsgraphen, Codierungstheorie, randomisierte Algorithmen etc.). Als Anwendungen sollen vor allem Fragen aus dem Bereich der Graphentheorie besprochen werden.

Als Grundlage dienen die Bücher

• [AS] N. Alon, J. H. Spencer, The probabilistic method, Wiley 2000.
• [B] B. Bollobás, Modern Graph Theory, Springer 1998.
• [Z] G. M. Ziegler, Lectures on Polytopes, Springer 1995.

Kriterium für den Scheinerwerb ist ein Vortrag mit Ausarbeitung.
Ich erwarte eine aktive Beteiligung meiner Diplomanden an diesem Seminar.

Termin: Dienstag, den 22.04. um 14:00 im D1.320

Themen

• Kombinatorik der Linearen Programmierung (Teil 1)
  Michael Hußmann, 20. Mai
  Ausarbeitung: [ ps | pdf ]
  
  Hirsch' Vermutung und d-step Conjecture
  Betreuung: Martin Ziegler
  
  Literatur:
  • V. Klee, D. Walkup, The d-step conjecture for polyhedra of dimension d<6, Acta Math. 117, pp.53-78 (1967).
  • V. Klee, P. Kleinschmidt, The d-step conjecture and its relatives, Math. Oper. Res. 12, pp.718-755 (1987).
  • F. Holt, V. Klee, Counterexamples to the Strong d-step conjecture for d>=5, Discrete Computat. Geom. 19, pp.33-46 (1998).
  • [Z], Kapitel 3.
  
  
  
• Kombinatorik der Linearen Programmierung (Teil 2)
  Martin Hirsch, 27. Mai
  Ausarbeitung: [ ps | pdf ]
  
  Beweis der 5-step Conjecture
  Betreuung: Martin Ziegler
  
  Literatur:
  • V. Klee, D. Walkup, The d-step conjecture for polyhedra of dimension d<6, Acta Math. 117, pp.53-78 (1967).
  • V. Klee, P. Kleinschmidt, The d-step conjecture and its relatives, Math. Oper. Res. 12, pp.718-755 (1987).
  • F. Holt, V. Klee, Counterexamples to the Strong d-step conjecture for d>=5, Discrete Computat. Geom. 19, pp.33-46 (1998).
  • [Z], Kapitel 3.
  
  
  
• Martingale und grosse Abweichungen
  Sascha Tiemeyer, 3. Juni
  
  Motivation: Chernov Schranke(n)
  Grundbegriffe zu zeitdiskreten Martingalen.
  Azumas Ungleichung
  Anwendung auf die chromatische Zahl
  
  Literatur:
  • [AS], Kap. 7.
  • Siehe auch: C. McDiarmid, Concentration, in Probabilistic Methods for algorithmic discrete mathematics, Algorithms and Combinatorics 16, Springer 1998, pp. 195-248.
  
  
• Das Tutte Polynom
  Anna Barát, 17. Juni
  Ausarbeitung: [ ps | pdf ]
  
  Verschiedene Charakterisierungen: Schneide- und Klebeoperationen, spannende Bäume, Whitney's Rang-erzeugendes Polynom
  Zusammenhänge zur statistischen Physik (Partitionsfunktion) und zur Knotentheorie (Jones Polynom, Kauffman Klammer)
  Betreuung: Martin Lotz
  
  Literatur:
  • [B], Kap. X.
  • Siehe auch: D.J.A. Welsh, Complexity: Knots, Colourings and Counting, London Math. Soc. Lect. Note Ser., vol. 186, Cambridge Univ. Press, 1993.
  
  
• Eigenwerte von Graphen
  Andreas Kottmann, 24. Juni
  
  Abstecher über algebraische Graphentheorie
  Zusammenhänge zwischen den Eigenwerten der Adjazenzmatrix und typischen Grössen von Graphen (Grad, chromatische Zahl, Zusammenhang, etc.)
  
  Literatur:
  • [B], VIII.2.
  
  
• Irrfahrten auf Graphen (zwei Vorträge)
  (eventuell noch zu vergeben)
  
  Markovketten
  Zusammenhänge mit elektrischen Netzwerken
  Leitfähigkeit und schnelles Mischen
  
  Literatur:
  • [B], Kap. IX.