Extremal Graph Theory (Summer Semester 2016)
- Lecturer: Prof. Dr. Maria Axenovich
- 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. Dr. Maria Axenovich | |
| Office hours: Mon. 13:00-14:00 (available per e-mail or Skype) | ||
| 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 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,
)
- classical theorems on matchings and cycles
- Regularity lemma and applications
- Erdös-Stone-Simonovits' theorem for ex(n,H)
- ex(n,
)
- ex(n,
)
- extremal numbers for hypergraphs
- r(
- r(
,
- 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
- R. Diestel -- Graph Theory (free onlone edition available on http://diestel-graph-theory.com)
- B. Bollobas -- Extremal Graph Theory
- Supplementary materials for Erdös-Stone Theorem
- Frankl-Wilson construction of a lower bound for Ramsey numbers
- Probabilistic upper bound on r(3,n) (from: N. Alon, J.H. Spencer -- The Probabilistic Method, p. 272-273)
- Recursive upper bound for Ramsey numbers of Hypergraphs
- Recursive upper bound for Ramsey numbers of 3-uniform Hypergraphs (triple systems)
- Missing proof from the lecture on July 15 (Lemma 2, Lecture 8)