Ekstremalna teoria grafów 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).
Rodzaj przedmiotu
Wymagania (lista przedmiotów)
Koordynatorzy przedmiotu
Efekty kształcenia
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.
Kryteria oceniania
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.
Literatura
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
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: