Home | english | Impressum | Sitemap | Intranet | KIT
Arbeitsgruppe Diskrete Mathematik

Sekretariat
Kollegiengebäude Mathematik (20.30)
Zimmer 1.044

Adresse
Institut für Algebra und Geometrie
Englerstr. 2
D-76131 Karlsruhe

Öffnungszeiten:
Di, Do, Fr 8:30-12:00

Tel.: 0721 608 47412

Fax.: 0721 608 46968

Extremal Graph Theory (Sommersemester 2016)

Dozent: Prof. Maria Axenovich Ph.D.
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
Dozenten
Dozentin Prof. Maria Axenovich Ph.D.
Sprechstunde: Montags 15:40-16:40
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 K_n 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,K_t)
  • Klassische Aussagen über Matchings und Kreise
  • Regularity Lemma und Anwendungen
  • Erdös-Stone-Simonovits Theorem über ex(n,H)
  • ex(n,K_{s,t})
  • ex(n,C_k)
  • Extremalzahlen für Hypergraphen
  • r(K_t)
  • r(K_3,K_t)
  • 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