Research Group Lattice Polytopes

Die Klausureinsicht ist am Freitag, den 9.4. um 11:45 in Raum 202, A3.

Die Nachklausur wurde am Freitag, den 26.3.2010 von 10-12 im Hörsaal 001 in der Arnimallee 3 geschrieben.
Wenn Sie mitgeschrieben haben und der Veröffentlichung Ihrer Note auf dieser Seite zugestimmt haben, können Sie Ihr Ergebnis mit diesem Link abfragen. (Sowohl Benutzername als auch Passwort sind Ihre Matrikelnummer). Wenn Sie dem Aushang an meiner Bürotür zugestimmt haben, können Sie dort nachsehen.

Ich wünsche Ihnen einen guten Start ins neue Semester.
Wenn Sie weiterhin Interesse an Diskreter Mathematik haben, dann können Sie im nächsten Semester zwischen zwei Fortsetzungen zu dieser Vorlesung wählen:

• Der Kurs Combinatorics von Tibor Szabo behandelt (nach einer kurzen Einführung) Ramseytheorie, extremale und strukturelle Graphentheorie und kombinatorische Methoden. Der Kurs wird auf Englisch gehalten und ist Teil des BMS-Vorlesungsangebots.
• Ich werde eine Vorlesung Geometrie und Optimierung anbieten. In dieser Vorlesung werden wir uns mit Polyedertheorie, Dualität, linearer und ganzzahliger Optimierung, dem Simplexverfahren und Methoden zur ganzzahligen Optimierung sowie Anwendungen der Methoden in Graphentheorie und anderen Gebieten beschäftigen.

Die Vorlesung wird sich hauptsächlich mit Graphentheorie und abzählender Kombinatorik beschäftigen.

Wir werden uns am Anfang mit Graphentheorie beschäftigen. Bisher habe ich für die Vorlesung die folgenden Themen vorgesehen:

• Graphen und gerichtete Graphen: Grundbegriffe
• Bäume, aufspannende Bäume, kürzeste Wege
• Ebene Graphen
• Färbungen
• Matchings
• Netzwerke und Flüsse

Im zweiten Teil Konzentrieren wir uns auf Zählprinzipien.

• Elementare Zählprinzipien
• Erzeugende Funktionen
• Rekurrenzen
• Techniken: Summation, Inklusion-Exklusion
• Polya-Theorie

Zwischendrin beschäftigen wir uns mit Matroiden, endlichen und linearen Codes oder Inzidenzstrukturen. Hier können auch von Seiten der Hörer Wünsche geäußert werden,

• Vorlesung:
  • Dienstag 12.00 - 14.00, SR 31 (Arnimallee 6)
  • Donnerstag 13.40 - 14.40, SR 31 (Arnimallee 6)
  
  
• Übungen:
  • Do 12.00 - 13.30
    

Hier wird nach und nach eine stichwortartige Zusammenfassung der Vorlesungen erscheinen.

Datum	Inhalt
13.10.	Einführung Termine, Übungen, Klausur Definition von Graphen, Begriffe.
15.10.	Termine, Übungen Beispiele von Graphen: regulär, vollständig, (vollständig) biparit, Untergraphen Wege, Pfade, Kreise, Zusammenhang
20.10.	Wege, Kreise, Abstand Löschen von Knoten, Kanten; Schnittknoten, Brücken Vereinigung, Schnitt allgemeinere Graphenklassen, gerichtete Graphen Bäume Wälder, Bäume, minimal zusammenhängend, maximal kreisfrei Anzahl Kanten
22.10.	Chrarakterisierung von Bäumen aufspannende Bäume Breitensuche
27.10.	Breitensuche Tiefensuche minimal auspannende Bäume Algorithmus von Kruskal für MST
29.10.	Algorithmus von Kruskal für MST Laufzeit Satz von Cayley,Prüferfolgen Ebene Graphen Definitionen Eulerformel Lineare Kantenschranke
03.11.	K3,3 und K5 sind nicht eben. Satz von Kuratowski (ohne Beweis) Polytopgraphen Färbungen chromatische Zahl Cliquen, unabhängige Mengen Approximationsalgorithmus für Färbungen
05.11.	Schranken durch Maximalgrad Satz von Brooks
10.11.	Satz von Brooks Färbungen von ebenen Graphen Satz von Kempe/Heawood Matchings Definitionen, maximum/maximal/perfektes Matching, alternierende, vergrößernde Pfade Satz von Berge
12.11.	Marriage Theorem
17.11.	Theorem of König-Egervary perfect matchings: Theorem of Dirac perfect matchings: Theorem of Tutte Networks weight functions shortest path problem Dijkstra's algorithm
19.11.	Flüsse Schnitte s-t-vergrößernde Pfade
24.11.	MaxFlow-MinCut-Satz ganzzahlige Flüsse und Pfadzerlegung kantendisjunkte und kreuzungsfreie Wege Satz von Menger: Kanten- und Knotenversion k-facher (Kanten-)Zusammenhang
26.11.	k-facher (Kanten-)Zusammenhang Abzählen Elementare Zählprinzipien, Schubfachprinzip
01.12.	Elementare Zählprinzipien Permutationen, Kombinationen Partitionen, Stirlingzahlen zweiter Art
03.12.	Elementare Zählprinzipien Stirlingzahlen zweiter Art Partitionen
08.12.	Zusammenfassung der Zählprinzipien Identitäten Inklusion-Exklusion Formel für Stirlingzahlen
10.12.	Eulersche φ-Funktion Möbius-Funktion, Möbius-Inversion
15.12.	Möbius-Funktion, Möbius-Inversion Lemma von Burnside Erzeugendenfunktionen Definition, Beispiel
17.12.	Zählprobleme und Erzeugendenfunktionen Rekursionen
05.01.	Formale Potenzreihen, Ringstruktur, Eigenschaften Beispiel: Rekursionen, Partitionen
07.01.	Exponentielle Potenzreihen Zählen von Permutationen fixpunktfreie Permutationen
12.01.	Partitionen Rekursionen, Partitionen für kleines n unterschiedliche Summanden Satz von Euler
14.01.	Erzeugendenfunktion spezielle Partitionen Beweise über Erzeugendenfunktion/ Identiäten
19.01.	Catalanzahlen Definition, Formel Beispiele, Klammerungen, Gitterpfade Erzeugendenfunktion
21.01.	Polya-Theorie Gruppen und Gruppenwirkung Beispiele von Gruppen
26.01.	Orbiten, Muster, Fixpunktmengen Lemma von Burnside Zykelindex
28.01.	Gewichtsfunktion, Mustererzeugendenfunktion (pattern inventory) Satz von Polya
02.02.	Satz von Polya, Beispiele Permutationen auf den Farben
04.02.	Permutationen auf den Farben Graphen zählen

Die Übungsaufgaben sollen in Zweier- oder Dreiergruppen bearbeitet und abgegeben werden. Sie müssen bis spätestens am auf die Ausgabe folgenden Dienstag vor der Vorlesung abgegeben werden (Ausnahme: ersten Blatt bis Donnerstag vor dem Tutorium).

Datum	Thema	Abzugeben bis
15.10.	Wege und Kreise in Graphen	22.10.
20.10.	Bäume	27.10.
27.10.	aufspannende Bäume, DFS, BFS	03.11.
3.11.	minimal aufspannende Bäume, ebene Graphen	10.11.
10.11.	Färbungen	17.11.
17.11.	Matchings	24.11.
24.11.	Zusammenhang	01.12.
01.12.	Schubfachprinzip	08.12.
08.12.	Zählen	15.12.
15.12.	Zählen, Erzeugendenfunktionen	05.01.
05.01.	Erzeugendenfunktionen	12.01.
12.01.	Erzeugendenfunktionen	19.01.
19.01.	Catalan- und andere Zählfunktionen	26.01.
26.01.	Zählen unter Symmetrie	02.02.
02.02.	Zusatzblatt	09.02.

Ab Mitte Oktober können Sie eine kleine Auswahl an Büchern im Handapparat zur Vorlesung finden.

[Tu]	Alan Tucker Applied Combinatorics, Wiley
[HHM]	John Harris, Jeffry L. Hirst, and Michael J. Massinghoff Combinatorics and Graph Theory, Springer
[vLW]	van Lint und Wilson A course in Combinatorics, Cambridge University Press
[Ste]	Angelika Steger Diskrete Strukturen, Springer
[LPV]	Lovasz, Pelikan, Vesztergombi Discrete Mathematics, Springer

Um die ECTS-Punkte für diesen Kurs zu bekommen, müssen Sie

• regelmäßig am Tutorium teilnehmen (was bedeutet, höchsten zweimal zu fehlen)
• Korrekte Lösungen zu mindestens 50% der ausgegebenen Übungsaufgaben einreichen.
• die Klausur am Ende des Semesters bestehen.