Home | deutsch  |  Impressum  |  Data Protection  |  Sitemap  |  Intranet  |  KIT
Research Group on Discrete Mathematics

Secretariat
Kollegiengebäude Mathematik (20.30)
Room 1.044

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

Office hours:
Tu, Th, F 8:30-12:00

Tel.: +49 721 608 47412

Fax.: +49 721 608 46968

Extremal Graph Theory (Summer Semester 2018)

Lecturer: Prof. Dr. Maria Axenovich, Yelena Yuditsky
Classes: Lecture (0150400), Problem class (0150410)
Weekly hours: 4+2


Announcements
Schedule
Lecture: Monday 14:00-15:30 -1.015 (20.30)
Wednesday 9:45-11:15 -1.015 (20.30)
Problem class: Monday 17:30-19:00 SR 1.067 (20.30)
Lecturers
Lecturer, Problem classes Yelena Yuditsky
Office hours: Mondays 15:30-17:30 (and upon request)
Room 1.045 Kollegiengebäude Mathematik (20.30)
Email: yelena.yuditsky@kit.edu

The course will cover fundamental results and tools in the field as well as several recent advances. The topics will include extremal functions, structure of extremal graphs, Szemerèdi's regularity lemma, Ramsey theory for graphs and hypergraphs, and graph colorings.

Lectures Topics
  • Lecture 1: Mantel and Turán theorems.
  • Lecture 2: Hall and Dirac theorems, trees with t edges in graphs with average degree 2t.
  • Lecture 3: Erdös-Stone-Simonovits theorem.
  • Lecture 4: Finishing the proof of Erdös-Stone-Simonovits theorem and Szemerédi's regularity lemma.
  • Lecture 5: Finishing the proof of Szemerédi's regularity lemma.
  • Lecture 6: The counting lemma for triangles and triangle removal lemma.
  • Lecture 7: Roth's theorem and the counting lemma for any graph H.
  • Lecture 8: Alternative proof for the Erdös-Stone-Simonovits theorem, bounds on ex(n,K_{s,t}).
  • Lecture 9: Dependent random choice and a bound on ex(n,H) for a bipartite graph H.
  • Lecture 10: Some lemmas needed for the proof of the extremal number of an even cycle.
  • Lecture 11: A proof for the extremal number of an even cycle.
  • Lecture 12: Finishing the proof of the extremal number of an even cycle. Extremal number of an odd cycle.
  • Lecture 13: Finishing the proof of the extremal number of an odd cycle.
  • Lecture 14: Extremal numbers of hypergraphs and Turán densities.
  • Lecture 15: More on extremal numbers of hypergraphs and Turán densities.
  • Lecture 16: Graph Ramsey numbers, some upper bounds.
  • Lecture 17: Graph Ramsey numbers, some lower bounds.
  • Lecture 18: Shearer's proof for the Ajtai, Komlós and Szemerédi's theorem about an upper bound on r(3,n).
  • Lecture 19: Hypergraph Ramsey numbers.
  • Lecture 20: Ramsey numbers r(H,G) for some general graphs H,G.
  • Lecture 21: Proof of r(H)\le c(\Delta)|V(H)| for a graph H with maximum degree \Delta.
  • Lecture 22: Proof of the existence of a graph H with maximum degree \Delta for which r(H)\ge 2^{c\Delta} |V(H)|.
  • Lecture 23: Proof of r(H)\le 2^{c\Delta}|V(H)| for a bipartite graph H with maximum degree \Delta.
  • Lecture 24: Finishing the proof of r(H)\le 2^{c\Delta}|V(H)| for a bipartite graph H with maximum degree \Delta.
  • Lecture 25: Ramsey numbers of degenerate graphs.
  • Lecture 26: Size Ramsey numbers and on-line Ramsey numbers.
  • Lecture 27: Review lecture.

Exercise Sheets

We will publish an exercise sheet each week on this website. You may submit written solutions in the problem class on Monday. We will check these solutions, but there are no points or grades on this homework.

We strongly encourage you to work on these exercises to practice solving problems and to get used to the material from the lecture. The solutions will be discussed in the problem class and published on this website.

(The questions are mostly taken from a question data base compiled by Jonathan Rollin.)

Examination

There will be an oral exam at the end of the semester.

Literature

The main source of this course are lecture notes which will be distributed to the students.

Other sources include (and will be updated during the semester):