Seminar über Kombinatorik SS 2003

Prof. Dr. Peter Bürgisser


Aktuell: Seminarbeginn wurde um eine Woche verschoben!


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.