Webrelaunch 2020

Extremal Graph Theory (Summer Semester 2016)

Schedule
Lecture: Tuesday 11:30-13:00 SR 2.59
Friday 9:45-11:15 SR 2.59
Problem class: Thursday 14:00-15:30 SR 3.69
Lecturers
Lecturer Prof. Dr. Maria Axenovich
Office hours: Fr. 10:00-11:00
Room 1.043 Kollegiengebäude Mathematik (20.30)
Email: maria.aksenovich@kit.edu
Problem classes Jonathan Rollin
Office hours: Friday, 15:30-16:30
Room 1.039 Kollegiengebäude Mathematik (20.30)
Email: jonathan.rollin@kit.edu

The extremal function ex(n,H) for a graph H is the largest number of edges in a graph on n vertices that does not contain H as a subgraph. The Ramsey function r(H) for a graph H is the smallest integer n such that in any 2-coloring of the edges of a complete graph K_n on n vertices there is a monochromatic copy of H.

In this course the properties of these functions and their generalizations are considered. In addition, other extremal results are discussed.

Specific topics include:

  • Turan's theorem for ex(n,K_t)
  • classical theorems on matchings and cycles
  • Regularity lemma and applications
  • Erdös-Stone-Simonovits' theorem for ex(n,H)
  • ex(n,K_{s,t})
  • ex(n,C_k)
  • extremal numbers for hypergraphs
  • r(K_t)
  • r(K_3,K_t)
  • hypergraph Ramsey numbers
  • Ramsey numbers for graphs of bounded maximum degree and arrangeable graphs
  • size and online Ramsey numbers

Exercise Sheets

We will publish an exercise sheet each week on this website. You may submit written solutions in the problem class on Thursday. 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 webiste.


Examination

There will be oral exams at the end of semester.

Students may choose one out of four given days for their exam. Please register for the exam in the secretariat (room 1.044) or in the lecture. Additionally you need to register online.


Literature

The main source of this course are lecture notes from David Conlon (University of Oxford) for courses in


Other sources include