Ekstremalna teoria grafów
Informacje ogólne
Kod przedmiotu: | 1000-2M22ETG |
Kod Erasmus / ISCED: |
11.3
|
Nazwa przedmiotu: | Ekstremalna teoria grafów |
Jednostka: | Wydział Matematyki, Informatyki i Mechaniki |
Grupy: |
Przedmioty obieralne dla informatyki Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka |
Punkty ECTS i inne: |
6.00
|
Język prowadzenia: | angielski |
Rodzaj przedmiotu: | monograficzne |
Wymagania (lista przedmiotów): | Matematyka dyskretna 1000-212bMD |
Skrócony opis: |
The course gives an introduction to extremal graph theory, a branch of graph theory which studies how global parameters of a graph, such as its edge density or chromatic number, can influence its local substructures (for instance, how many edges can a graph on n vertices have without containing a triangle). After introducing the basic results and tools of the subject, the course will focus on the celebrated Szeméredi regularity lemma and its applications, and in the last part of the lecture we will introduce modern and interesting theory of graph limits. Note: Course is given in English. |
Pełny opis: |
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). |
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 |
Efekty uczenia się: |
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. |
Metody i 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. |
Zajęcia w cyklu "Semestr zimowy 2023/24" (zakończony)
Okres: | 2023-10-01 - 2024-01-28 |
Przejdź do planu
PN WT WYK
CW
ŚR CZ PT |
Typ zajęć: |
Ćwiczenia, 30 godzin
Wykład, 30 godzin
|
|
Koordynatorzy: | Jakub Gajarský | |
Prowadzący grup: | Jakub Gajarský | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Egzamin |
Zajęcia w cyklu "Semestr letni 2024/25" (jeszcze nie rozpoczęty)
Okres: | 2025-02-17 - 2025-06-08 |
Przejdź do planu
PN WT ŚR CZ PT |
Typ zajęć: |
Ćwiczenia, 30 godzin
Wykład, 30 godzin
|
|
Koordynatorzy: | Jakub Gajarský | |
Prowadzący grup: | Jakub Gajarský | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Egzamin |
Właścicielem praw autorskich jest Uniwersytet Warszawski.