Algorithms and Complexity - Main page Algorithms and Complexity

Seminar: Extremale Kombinatorik

Dozent: Mathias Schacht

Termine

Beginn des Seminars: 20.10.2005.
SE Donnerstag 15:00 - 17:00 (RUD 25, 4.112)
Sprechzeit Dienstag 13:00 - 17:00 (RUD 25, 3.416)

Zuordnung

  • Hauptstudium, Seminar

Inhalte und Lernziele

Anhand klassischer und aktueller Forschungsergebnisse sollen verschiedene Techniken der Diskreten Mathematik vorgestellt werden. Im Vordergrund stehen hier algebraische und probabilistische Methoden, welche in den letzten Jahren viele Anwendungen in der theoretischen Informatik und extremalen Kombinatorik hatten.

Voraussetzungen

  • Grundkenntnisse in diskreter Mathematik, Wahrscheinlichkeitstheorie und linearer Algebra
  • Der Besuch von Graphen und Algorithmen 1 ist hilfreich, aber nicht notwendig.

Vortragsthemen

20.10.05 Mathias Schacht Einführung und Themenvergabe
27.10.05 Mathias Schacht Gegenbeispiel zur Vermutung von Borsuk
17.11.05 Geneviève Grunert Satz von Erdős-Ko-Rado
24.11.05 Thomas Pillat Beweis der Stanley-Wilf Vermutung
08.12.05 Katharina Marzok Satz von Ahlswede und Khachatrian über sich überschneidende Mengenfamilien I
15.12.05 Katharina Marzok Satz von Ahlswede und Khachatrian über sich überschneidende Mengenfamilien II
19.01.05 Thomas Meyer Konstruktive Ramseyschranken
26.01.06 Kay Schoenberger Faktorisierungsalgorithmen I
02.02.06 Kay Schoenberger Faktorisierungsalgorithmen II
09.02.06 Hiêp Han Asymptotisch exakte Schranken für einige mehrfarbige Ramseyzahlen

Literatur

  • S. Jukna, Extremal Combinatorics. With applications in computer science, Springer, 2001
  • R. Graham, B. Rothschild und J. Spencer, Ramsey Theory, Wiley, 1990
  • N. Alon und J. Spencer, The Probabilistic Method, Wiley, 2000
  • L. Babai und P. Frankl, Linear Algebra Methods in Combinatorics, Preliminary Version 2, University of Chicago
  • B. Bollobás, Extremal graph theory, Academic Press, Inc., 1978
last modified 09/23/09 (alkox-www)