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