Home | deutsch | Impressum | 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 2016)

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


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. Maria Axenovich Ph.D.
Office hours: Mondays 15:40-16:40
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