Uniwersytet Warszawski - Centralny System Uwierzytelniania
Strona główna

Ekstremalna teoria grafów

Informacje ogólne

Kod przedmiotu: 1000-2M22ETG
Kod Erasmus / ISCED: 11.3 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0612) Database and network design and administration Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
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 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.

zobacz reguły punktacji
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
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Jakub Gajarský
Prowadzący grup: Jakub Gajarský
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.
ul. Banacha 2
02-097 Warszawa
tel: +48 22 55 44 214 https://www.mimuw.edu.pl/
kontakt deklaracja dostępności USOSweb 7.0.3.0-2b06adb1e (2024-03-27)