Ausgewählte Themen der diskreten Mathematik, Sommersemester 2002

Hinweise, Fragen etc. sind jederzeit willkommen.

Aus dem kommentierten Stundenplan:
Ein moderner Zweig der diskreten Mathematik beschäftigt sich mit der Frage, ob nicht jede genügend große, noch so unregelmäßige Struktur reguläre Teilstrukturen haben muß. Betrachtet man z.B. den Sternenhimmel, so kann man darin ja sehr wohl auch Muster erkennen. (Ordnung im Chaos!) Dieses Phänomen taucht in verschiedenen Gebieten der diskreten Mathematik auf. In dieser Vorlesung werden wir besonders Beispiele in Geometrie, Graphentheorie, Ramseytheorie, Zahlentheorie (Primzahlen, Siebmethoden) und evtl. Diskrepanztheorie behandeln. Ebenso werden wir algorithmische Aspekte ansprechen: Wie kann man große Mengen mit "guten" Eigenschaften konstruieren?
Vorkenntnisse in Graphentheorie und Zahlentheorie sind nützlich, werden aber auch im Rahmen der Vorlesung bereitgestellt. Die Vorlesung ist so konzipiert, dass man das meiste ab dem 4. Semester verstehen kann.
Zielgruppe: Studenten aller mathematischen Studiengänge und der Informatik.

Da die urpsrünglich vorgesehene Vorlesung Kombinatorik (bzw. Blockpläne/Endliche Geometrie) von Prof. Klotz nicht stattfinden kann, werde ich mir Mühe geben, auch dieses Thema mitabzudecken. Für Vorschläge bezüglich der Themenauswahl bin ich offen. Ich selber plane folgende Themen: Dazu nützliche Literatur habe ich in der Bibliothek als Semesterapparat bereitgestellt.
Inhalt:
  • Addition von Mengen ganzer Zahlen oder von Restklassen
  • Die Polynommethode (Combinatorial Nullstellensatz)
  • Die Erdos-Heilbronn-Vermutung
  • Der Satz von Chevalley and Warning
  • Summen von VERSCHIEDENEN Restklassen
  • Ein Gitterpunktproblem
  • Anwendung der Polynommethode auf reguläre Untergraphen
  • Anwendung der Polynommethode auf die Existenz spezieller Hyperebnen im R^n
  • Einen Kuchen gerecht teilen
  • Satz von Borsuk-Ulam, Pfannenkuchensatz, Schinkenbrötchensatz
  • Algorithmen, die eine gerechte Teilung von einem Kuchen garantieren. Praktische Anwendung desselben.
  • Ramseytheorie
  • Cliquen in großen beliebig gefärbten Graphen
  • Die probabilistische Methode
  • Algorithmische Bestimmung von Cliquen
  • Das Happy-End Problem (Klein-Szekeres)
  • Blockpläne
  • Verschiedene Konstruktionsverfahren:
  • Steinertripelsysteme
  • Endliche Differenzenmengen
  • Projektive Ebenen, affine Ebenen
  • Summen von Zwei Quadraten
  • Extremale Graphentheorie
  • Satz von Turan
  • Satz von Kövari-Sos-Turan
  • Analoge Resultate für Hypergraphen
  • Das Cube Lemma
  • Primzahlen
  • Wiederholung (Satz von Tschebyscheff)
  • Anwendung von Graphentheorie auf Primzahlfragen
  • Endliche Punktmengen in der Ebene