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
edges in graphs with average degree
.
- 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
.
- Lecture 8: Alternative proof for the Erdös-Stone-Simonovits theorem, bounds on
.
- Lecture 9: Dependent random choice and a bound on
for a bipartite graph
.
- 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
.
- Lecture 19: Hypergraph Ramsey numbers.
- Lecture 20: Ramsey numbers
for some general graphs
.
- Lecture 21: Proof of
for a graph
with maximum degree
.
- Lecture 22: Proof of the existence of a graph
with maximum degree
for which
.
- Lecture 23: Proof of
for a bipartite graph
with maximum degree
.
- Lecture 24: Finishing the proof of
for a bipartite graph
with maximum degree
.
- 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.
- Sheet 1, Sheet 1 solutions
- Sheet 2, Sheet 2 solutions
- Sheet 3, Sheet 3 solutions
- Sheet 4, Sheet 4 solutions
- Sheet 5, Sheet 5 solutions
- Sheet 6, Sheet 6 solutions
- Sheet 7, Sheet 7 solutions
- Sheet 8, Sheet 8 solutions
- Sheet 9, Sheet 9 solutions
- Sheet 10, Sheet 10 solutions
- Sheet 11, Sheet 11 solutions
(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):
- R. Diestel -- Graph Theory (free online edition available on http://diestel-graph-theory.com)
- B. Bollobás -- Extremal Graph Theory