Extremal graph theory 1000-2M22ETG
Basic results, such as Mantel’s theorem, Turán’s theorem, König’s theorem, Dirac’s theorem (2 lectures).
Erdös-Stone-Simonovits theorem (1 lecture).
Probabilistic tools in extremal graph theory (2 lectures).
Szeméredi regularity lemma: statement and proof, basic applications, Counting lemma, Triangle removal lemma, Roth’s theorem, basic application in property
testing, other regularity lemmas (4-5 lectures).
Graph limits: introduction and motivation, convergence of graphs, necessary tools from mathematical analysis, graphons, compactness of the space of graphons, relationship to extremal problems (4-5 lectures).
Type of course
Requirements
Course coordinators
Learning outcomes
Besides acquiring the knowledge of standard results and tools of extremal theory, the student knows the regularity lemma and its applications and has basic working knowledge of graph limits.
Assessment criteria
Oral exam.
The course can provide credit for doctoral students as a "methodological course". In that case, there is an additional requirement for passing the course: the student should correctly solve at least one of the selected problems given by the lecturer, or study and present a research paper assigned by the lecturer.
Bibliography
Lecture notes provided by the lecturer
“Graph theory”, Chapter 7, Reinhard Diestel
“Extremal graph theory”, Béla Bollobás
“Large networks and graph limits”, László Lovász
Research articles provided by the lecturer
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes:
- Bachelor's degree, first cycle programme, Computer Science
- Master's degree, second cycle programme, Computer Science
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: