Home | deutsch | Impressum | Sitemap | Intranet | KIT
Research Group on Discrete Mathematics

Secretariat
Kollegiengebäude Mathematik (20.30)
Room 1.044

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

Office hours:
Tu, Th, F 8:30-12:00

Tel.: +49 721 608 47412

Fax.: +49 721 608 46968

Seminar (Graph Colouring) (Winter Semester 2014/15)

Lecturer: Prof. Maria Axenovich Ph.D., Torsten Ueckerdt
Classes: Seminar (0121300)
Weekly hours: 2


This is a reading seminar based on the book Graph Colourings and the Probabilistic Method by Michael Molloy and Bruce Reed. Every student presents a part of this book in a talk.

A succesful participation includes:

  • presence
  • participation
  • a good talk
Schedule
Seminar: Wednesday 11:30-13:00 1C-01
Wednesday 11:30-13:00 SR 3.68
Lecturers
Lecturer Prof. Maria Axenovich Ph.D.
Office hours: Thursdays 15:40-16:40
Room 1.043 Kollegiengebäude Mathematik (20.30)
Email: maria.aksenovich@kit.edu
Lecturer Torsten Ueckerdt
Office hours: Mondays 2pm-3pm
Room 1.045 Kollegiengebäude Mathematik (20.30)
Email: torsten.ueckerdt@kit.edu

Prerequisites

  • basic knowledge of graph theory and probability theory

Procedure

  • Every student gives a talk on a chapter of the book assigned to him/her.
  • Every student attends two weeks before his/her talk personal meeting with Mr. Ueckerdt.
  • Every speaker may use the blackboard, the beamer and overhead transparencies. Handouts are optional.

Schedule

#part of the bookspeakerpages
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