Proseminar Kombinatorik - Sommersemester 2022

Dozent

Prof. Immanuel Halupczok (Sprechzeiten: nach Vereinbarung)

Termine

Mo, 14:30-16:00, Raum 25.13.U1.30
Am ersten Termin (am 4.4.) findet eine Vorbesprechung statt. Dort werden organisatorische Dinge geklärt, die Themen vorgestellt, Fragen beantwortet und Vortragsthemen vergeben.

Voraussetzungen

Lineare Algebra 1, Analysis 1

Dieses Proseminar richtet sich vor allem an Studierende im 2. oder 4. Semester.

Anmeldung

Wenn Sie Interesse haben, kontaktieren Sie mich am besten möglichst bald per Mail (gerne auch, wenn Sie noch nicht sicher sind, ob Sie teilnehmen möchten). Wenn Sie schon eine Vorstellung haben, für welches Vortragsthema Sie sich interessieren, können wir das gerne schon per Mail besprechen.

Falls am Vorbesprechungstermin (am 4.4.) noch Plätze frei sind, ist es auch möglich, sich dann vor Ort noch anzumelden.

Planung

Die bisherige Planung für die Vorträge ist die Folgende:

11.4.: I. Halupczok: Einführung
(18.4.: kein Proseminar; Ostermontag)
25.4.: C. Genua Noguera: Grundlagen
(2.5.: Proseminar fällt aus)
9.5.: G. Prosch: Der Satz vom Diktator
16.5.: Fortsetzung vom Satz vom Diktator
23.5.: J. Kleinheider: Summen-Berechnungen
30.5.: F. Laurinat: Graphen
13.6.: O. Volkova: Der Heiratssatz
20.6.: M. Fortmann: Probleme topologischen Ursprungs
27.6.: C. Sportolari: Orthogonale lateinische Quadrate
(4.7.: Proseminar fällt aus)
11.7.: C. Genua Noguera: Erzeugende Funktionen

Ablauf

Jede:r Teilnehmer:in hält einen 75-minütigen Vortrag zu einem vorher festgelegten Thema. Danach sind noch 15 Minuten Zeit für Fragen, Feedback und Diskussion.
Jeder Vortrag muss mindestens eine Woche vorher mit mir besprochen werden. Zu diesem Zeitpunkt sollten Sie Ihren Vortrag schon vollständig vorbereitet und zeitlich geplant haben. Bitte kontaktieren Sie mich rechtzeitig per Mail, um einen Termin für diese Besprechung zu vereinbaren.

Themenvorschläge

Die Kombinatorik ist ein Teilgebiet der Mathematik, das sich vor allem damit beschäftigt, zu zählen, wie viele Strukturen/Objekte von bestimmten Typen es gibt. Z.B.: Wie viele Möglichkeiten gibt, es die Zahlen 1, ..., n anzuordnen? Wie viele Möglichkeiten gibt es, ein n×n-Gitter so mit Zahlen 1 bis n zu füllen, dass jede Zahl in jeder Zeile und in jeder Spalte genau einmal auftaucht?

Fragen aus der Kombinatorik sind typischerweise sehr leicht zu formulieren, aber die Antwort kann manchmal sehr schwierig sein. In diesem Proseminar werden wir eine bunte Mischung aus kombinatorischen Fragen betrachten. Die Vorträge werden größtenteils unabhängig voneinander sein, jedoch zum Teil gemeinsame Methoden verwenden.

Vortragende können frei wählen, über welches kombinatorische Thema sie vortragen möchten. Hier sind zwei mögliche Quellen (die über die ULB zur Verfügung stehen):

Hier ist eine Liste von konkreten Themenvorschlägen aus den beiden obengenannten Büchern. Bei den mehrteiligen Themen kann jeder Teil ein eigener Vortrag sein, oder mehrere Teile können in einen Vortrag (mit weniger Details) zusammengefasst werden.

Grundlagen: Mengen und Auswahlen
[Tittmann: 1.1, 1.2] und [Jacobs-Jungnickel: I.1, I.2]
Anzahl der Teilmengen einer $n$-elementigen Menge, Anzahl der $k$-elementigen Teilmengen, Anzahl der Injektionen einer Menge in eine andere, Anzahl der Permutationen einer Menge und einer Multimenge, Auswahlen mit/ohne Wiederholung und mit/ohne Berücksichtigung der Reihenfolge
Partitionen und Verteilungen
- Teil 1: Partitionen von Mengen
  [Tittmann: 1.3]
  Anzahl der Möglichkeiten, eine Menge in $k$ Teilmengen / in beliebig viele Teilmengen zu zerlegen; Stirling-Zahlen, Bell-Zahlen
- Teil 2: Partitionen von natürlichen Zahlen
  [Tittmann: 1.4]
  Anzahl der Möglichkeiten, eine natürliche Zahl als Summe von natürlichen Zahlen zu schreiben; der Ferrers-Graph
- Teil 3: Verteilungen
  [Tittmann: 1.5]
  Anzahl der Möglichkeiten, $n$ Objekte auf $k$ Boxen zu verteilen, in verschiedenen Varianten und mit verschiedenen Nebenbedingungen
Erzeugende Funktionen
Viele kombinatorische Probleme lassen sich besonders elegant lösen, indem man die gesuchten Zahlen als Koeffizientan $a_n$ einer Potenzreihe $\sum_{n=0}^\infty a_n$ auffasst. Diese Potenzreihe nennt man die erzeugende Funktion des Problems.
- Teil 1: Einführung und Formale Potenzreihen
  [Tittmann: 2.1, 2.2]
  Motivation, mathematische Grundagen
- Teil 2: Anwendungen
  [Tittmann: 2.3, 2.4, 2.5]
  Übersetzen von Beziehungen zwischen kombinatorischen Problemen in Beziehungen zwischen den erzeugenden Funktionen; Beispielanwendungen
Rekurrenzgleichungen
Eine Rekurrenzgleichung drückt einen Wert $a_n$ als Funktion der $k$ Vorgänger aus: $a_n = f(a_{n-1}, \dots, a_{n-k})$. Sie tauchen häufig in kombinatorischen Problemen aus; typischerweise sucht man dann nach einer expliziten Formel für $a_n$.
- Teil 1: Einführung
  [Tittmann: 3.1, 3.2, evtl. 3.3]
  Beispiele, in denen Rekurrenzgleichungen auftrefen und Beispiele für Lösungsmethoden.
- Teil 2: Lineare Rekurrenzgleichungen
  [Tittmann: 3.4]
  Es wird gezeigt, dass lineare Rekurrenzgleichungen (d.h. bei denen die obige Funktion $f$ linear ist) immer explizit gelöst werden können.
Summen-Berechnungen
[Tittmann: 4.1, 4.2]
Oft muss man bei kombinatorischen Problem Summen $\sum_{i=1}^k a_k$ berechnen. In diesem Vortrag werden einige Möglichkeiten dafür vorgestellt.
Graphen
Es gibt viele kombinatorische Probleme (auch aus der realen Welt), die sich mit Hilfe von Graphen beschreiben lassen. Ein Graph ist ein kombinatorisches Objekt, das aus einer Menge von Punkten besteht, von denen manche durch eine Kante verbunden sind.
- Teil 1: Grundbegriffe und Spannbäume
  [Tittmann: 5.1,5.2]
  Graphen werden definiert, und als Beispielproblem wird die Anzahl der Spannbäume bestimmt
- Teil 2: Graphen und Matrizen
  [Tittmann: 5.3]
  Zu einem Graphen kann man mehrere Matrizen assozieren, die einige Rechnungen mit dem Graph vereinfachen.
- Teil 3: Zählen von Untergraphen
  [Tittmann: 5.4]
  Einige kombinatorische Probleme sind äquivalent zu Problemen der Form: Wie viele Untergraphen einer bestimmten Form hat ein Graph eines bestimmten Typs?
Der Heiratssatz
Wenn in einer Menge von Leuten manche sich mögen und manche nicht, unter welcher Bedingung kann man die Leute so zu Pärchen gruppieren, dass sich jedes Pärchen mag? Der Heiratssatz gibt eine genau-dann-wenn-Bedingung dafür an.
- Teil 1: Der Heiratssatz und Varianten davon
  [Jacobs-Jungnickel: II.1, II.2]
  Beweis des Heiratssatzes; Vorstellung von manchen der Varianten aus II.2.
- Teil 2: Das Schnitt-Fluss-Problem
  [Jacobs-Jungnickel: II.3]
  Ist ein Netzwerk aus verschieden dicken Rohren gegeben mit einem Eingang und einem Ausgang, wie viel Wasser kann dann durch das Netzwerk vom Eingang zum Ausgang strömen?
Orthogonale lateinische Quadrate
Ein lateinisches Quadrat ist eine $n \times n$-Matrix, bei der in jeder Zeile und in jeder Spalte jede Zahl $1, \dots, n$ genau einmal auftritt. Auf ähnlich kombinatorische Weise definiert man, wann zwei lateinische Quadrate orthogonal zueinander sind.
- Teil 1: Grundlagen und erste Resultate
  [Jacobs-Jungnickel: III.1, III.2]
- Teil 2: Endliche Körper
  [Jacobs-Jungnickel: III.3]
  Es werden alle endlichen Körper beschrieben, und es wird gezeigt, wie man damit maximal viele orthogonale lateinische Quadrate der Größe $q$ konstruieren kann, wenn $q$ einen Primzahlpotenz ist.
- Teil 3: Weitere Konstruktionen von orthogonalen lateinische Quadraten
  [Jacobs-Jungnickel: III.4-III.6]
- Teil 4: Anwendung in der Kryptographie
  [Jacobs-Jungnickel: III.7]
  Ein Problem aus der Kryptographie besteht darin, dass ein Empfänger einer Nachricht sicher sein möchte, dass die Nachricht wirklich vom Sender kam und nicht unterwegs verändert wurde. Dies ist mit Hilfe von orthogonalen Arrays möglich.
Der Satz vom Diktator
[Jacobs-Jungnickel: IV]
Wenn man gewisse (sehr naheliegende) Forderungen an ein demokratisches Wahlsystem stellt, bleibt als einzige Möglichkeit, unter allen Wählern zufällig einen "Diktator" auszuwählen (d. h. diesen Wähler alleine entscheiden zu lassen).
Fastperiodische Folgen
[Jacobs-Jungnickel: V]
Zahlenfolgen, die sich zwar nie komplett wiederholen, aber "Stückweise"; ein besonders schönes Beispiel ist die Thue-Morse-Folge
Der Satz von Ramsey
[Jacobs-Jungnickel: VI]
Wenn man jeder $k$-elementigen Menge der natürlichen Zahlen eine von endlich vielen Farben zuordnet, kann man dann eine unendliche Menge $M \subset \mathbb N$ finden, so dass alle $k$-elementigen Teilmengen von $M$ die gleiche Farbe haben?

Spätere Kapitel aus den beiden Büchern sind natürlich auch als Themen möglich.

Tipps zur Vortragsvorbereitung

Das Ziel Ihres Vortrags sollte sein, Ihr Thema so vorzustellen, dass es für die anderen Seminarteilnehmer interessant ist. Mir ist es wichtig, dass die Zuhörer Spaß an Ihrem Vortrag haben, und nicht, ob irgendwelche Beweise vollständig von vorne bis hinten vorgetragen werden. (Das wichtigste, was Sie selbst dabei lernen sollten, ist nicht die Mathematik, sondern wie man mathematische Vorträge hält.)
Bevor Sie Ihren Vortrag planen, sollten Sie selbst Ihr Thema richtig verstanden haben. Es ist nicht möglich, einen guten Vortrag über etwas zu halten, was man selbst nicht vestanden hat. Wenn Sie Verständnisschwierigkeiten haben, kann ich Sie unterstützen; kontaktieren Sie mich bitte rechtzeitig.
Nachdem Sie viel Zeit darin investiert haben, etwas zu vestehen, werden Sie vielleicht das Bedürfnis haben, das auch alles vorzutragen. Wahrscheinlich werden Sie aber viel mehr Material haben, als in 75 Minuten passen; Ihre Aufgabe ist also inbesondere, eine geeignete Auszuwahl zu treffen. Insbesondere sollten Sie Beweise oder technische Details weglassen, die langweilig oder (in der Kürze der Zeit) unverständlich wären. Statt dessen werden Dinge oft durch Beispiele viel verständlicher. (Sie können sich überlegen: Wie würden Sie selbst sich eine Vorlesung zu Ihrem Thema wünschen?)