Home | english | Impressum | Sitemap | Intranet | KIT
Arbeitsgruppe Diskrete Mathematik

Sekretariat
Kollegiengebäude Mathematik (20.30)
Zimmer 1.044

Adresse
Institut für Algebra und Geometrie
Englerstr. 2
D-76131 Karlsruhe

Öffnungszeiten:
Di, Do, Fr 8:30-12:00

Tel.: 0721 608 47412

Fax.: 0721 608 46968

Seminar (Graph Colouring) (Wintersemester 2014/15)

Dozent: Prof. Maria Axenovich Ph.D., Torsten Ueckerdt
Veranstaltungen: Seminar (0121300)
Semesterwochenstunden: 2


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
Dozenten
Seminarleitung Prof. Maria Axenovich Ph.D.
Sprechstunde: Montags 15:40-16:40
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