Extremal Graph Theory (Sommersemester 2016)
- Dozent*in: Prof. Dr. Maria Axenovich
- Veranstaltungen: Vorlesung (0150400), Übung (0150410)
- Semesterwochenstunden: 4+2
| Termine | ||
|---|---|---|
| Vorlesung: | Dienstag 11:30-13:00 | SR 2.59 |
| Freitag 9:45-11:15 | SR 2.59 | |
| Übung: | Donnerstag 14:00-15:30 | SR 3.69 |
| Lehrende | ||
|---|---|---|
| Dozentin | Prof. Dr. Maria Axenovich | |
| Sprechstunde: Mon. 16:00-17:00 | ||
| Zimmer 1.043 Kollegiengebäude Mathematik (20.30) | ||
| Email: maria.aksenovich@kit.edu | Übungsleiter | Jonathan Rollin |
| Sprechstunde: Freitag, 15:30-16:30 | ||
| Zimmer 1.039 Kollegiengebäude Mathematik (20.30) | ||
| Email: jonathan.rollin@kit.edu | ||
Die extremale Funktion ex(n,H) beschreibt, für einen Graphen H, die größte Anzahl an Kanten in Graphen mit n Knoten, welche H nicht als Teilgraph enthalten. Die Ramsey Funktion r(H) beschreibt, für einen Graphen H, die kleinste Zahl n, sodass es in jeder 2-Färbung der Kanten eines vollständigen Graphen mit n Knoten eine einfarbige Kopie von H gibt.
In dieser Vorlesung werden Eigenschaften dieser Funktionen und Ihrer Verallgemeinerungen betrachtet. Zusätzlich, werden weitere Ergebnisse aus der extremalen Graphentheorie vorgestellt.
Unter anderem werden folgende Themen behandelt:
- Turan's Theorem über ex(n,
)
- Klassische Aussagen über Matchings und Kreise
- Regularity Lemma und Anwendungen
- Erdös-Stone-Simonovits Theorem über ex(n,H)
- ex(n,
)
- ex(n,
)
- Extremalzahlen für Hypergraphen
- r(
- r(
,
- Ramseyzahlen für Hypergraphen
- Ramseyzahlen für Graphen mit beschränktem Maximalgrad
- Kanten- und Online-Ramseyzahlen
Übungsblätter
Jede Woche wird hier ein Übungsblatt veröffentlicht. Lösungen zu diesen Aufgaben können in der Übung abgegeben werden. Diese Lösungen werden korrigiert, es gibt aber keine Punkte oder Noten für die Hausaufgaben.
Wir empfehlen es sehr die Übungsaufgaben zu bearbeiten, um den Vorlesungsstoff zu wiederholen und das Lösen von Problem zu üben. Die Lösungen zu den Aufgaben werden in der Übung besprochen und hier veröffentlicht.
Prüfung
Am Ende des Semesters kann eine mündliche Prüfung abgelegt werden.
Es stehen vier Termine zur Auswahl. Die Anmeldung zur Prüfung erfolgt im Sekretariat bei Frau Colin (Zimmer 1.044) oder direkt in der Vorlesung. Zusätzlich muss auch eine Anmeldung im Onlinesystem erfolgen.
Literaturhinweise
Die Vorlesung orientiert sich hauptsächlich an Vorlesungsmitschriften von David Conlon (Universität Oxford) für
Weitere Quellen sind
- R. Diestel -- Graph Theory (eine kostenlose Version gibt es auf http://diestel-graph-theory.com),
- B. Bollobas -- Extremal Graph Theory.
- Ergänzendes Material zum Erdös-Stone Theorem
- Frankl-Wilson Konstruktion einer unteren Schranke für Ramsey Zahlen
- Probabilistische obere Schrank an r(3,n) (aus: N. Alon, J.H. Spencer -- The Probabilistic Method, S. 272-273)
- Rekursive Abschätzung für Ramsey Zahlen von Hypergraphen
- Rekursive Abschätzung für Ramsey Zahlen von 3-uniformen Hypergraphen ("triple systems")
- Fehlender Beweis aus der Vorlesung vom 15. Juli (Lemma 2, Lecture 8)