Webrelaunch 2020

Seminar (Graph Colouring) (Wintersemester 2014/15)

Dies ist ein Lese-Seminar basierend auf dem Buch Graph Colourings and the Probabilistic Method von Michael Molloy und Bruce Reed. Jeder Student stellt einen Teil des Buches in einem eigens konzipierten Vortrag vor.

Zur erfolgreichen Teilnahme gehören:

  • Anwesenheit
  • Mitarbeit
  • ein guter Vortrag
Termine
Seminar: Mittwoch 11:30-13:00 1C-01
Mittwoch 11:30-13:00 SR 3.68
Lehrende
Seminarleitung Prof. Dr. Maria Axenovich
Sprechstunde: Mon. 13:00-14:00
Zimmer 1.043 Kollegiengebäude Mathematik (20.30)
Email: maria.aksenovich@kit.edu
Seminarleitung Torsten Ueckerdt
Sprechstunde:
Zimmer Kollegiengebäude Mathematik (20.30)
Email: torsten.ueckerdt@kit.edu

Vorraussetzungen

  • Grundkenntnisse in Graphentheorie und Wahrscheinlichkeitstheorie

Durchführung

  • Jeder Student gibt einen Vortrag über ein zugeteiltes Kapitel aus dem Buch.
  • Jeder Student trifft sich zwei Wochen vor seinem Vortragstermin mit Herrn Ueckerdt zu einer persönlichen Vorbesprechung.
  • Jeder Vortragende kann die Tafel, den Beamer und OHP-Folien benutzen. Handouts sind optional.

Zeitplan

#Abschnitt im BuchVortragenderSeiten
0.IntroductionTorsten--
1.First Moment MethodJohannes27-36
2.The Lovasz Local Lemma and The Chernoff BoundMatthias39-46
3.Hadwiger's ConjectureXizhe49-53
4.Total Colouring RevisitedDaniel67-75
5.Talagrand's InequalityAnnika79-89
6.Talagrand's InequalityJennifer79-89
7.Azuma's InequalityFabian91-103
8.Strucutral DecompositionFelix157-167
9.Chi, Omega and DeltaTorsten--
10.Near Optimal Total Colouring IAlexander185-191
11.Generalizations of the Local LemmaAnnette221-229
12.Finding Fractional ColouringsValentin239-246
13.Conditional Expectation and Algorithmic Local LemmaOussama287-291, 295-300