Mathematik Studium Mathematik Kursmaterialien SoSe 2022 Proseminar Kombinatorik

Proseminar Kombinatorik - Sommersemester 2022

Link zum LSF

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: 

Ablauf

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.
  1. 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
  2. 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
  3. 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
  4. 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.
  5. 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.
  6. 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?
  7. 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?
  8. 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.
  9. 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).
  10. 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
  11. 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