Wybrane zagadnienia teorii grafów (druga edycja)

semestr letni 2012/2013

Spis treści

Aktualności

Informacje ogólne

Przedmiot oferowany w semestrze letnim 2012/2013.
Strona przedmiotu w USOSie.
Podstrona poprzedniej edycji przedmiotu

Prowadzący

dr Marcin Pilipczuk, malcin@mimuw.edu.pl
(współprowadzący poprzedniej edycji: dr Jakub Onufry Wojtaszczyk, onufry@mimuw.edu.pl)

Warunki zaliczenia

  1. Podstawą zaliczenia są zadania domowe, udział w tworzeniu notatek z wykładu i egzamin ustny.
  2. W trakcie semestru będzie sześć serii po trzy zadania każda. Na każdą serię będzie przewidziany czas ok. 2-3 tygodni. Po upływie terminu zadania będą omawiane na ćwiczeniach i nie będzie można ich oddawać.
  3. Rozwiązania zadań należy oddawać pisemnie, najlepiej mailem do prowadzącego.
  4. Każde rozwiązanie oceniane jest jak na Olimpiadzie Matematycznej, tj może dostać 0, 2, 5 lub 6 pkt.
  5. W trakcie semestru będziemy tworzyli notatki z wykładów (i być może części ćwiczeń), tak jak to np. miało miejsce na tym wykładzie. Notowanie będzie podzielone po równo między uczestników przedmiotu.
  6. Notatki z n-tego wykładu należy: spisać w ciągu pięciu dni "roboczych" (czyli takich, w czasie których są zajęcia na MIMie), wysłać prowadzącym i następnie nanieść ich poprawki tak, by notatki były dostępne najpóźniej na wykładzie n+2, a możliwie wcześniej, jeśli po drodze z jakiś powodu nie ma wykładów.
  7. Za udział w tworzeniu notatek będzie można otrzymać do 36 punktów.
  8. Spóźnienie w notatkach jest oceniane następująco: spóźnienie do 2 tygodni: 90% punktów; oddanie przed egzaminem w czerwcu 70% punktów; oddanie przed egzaminem we wrześniu 50% punktów.
  9. Na koniec semestru, na podstawie liczby punktów przynajemy ocenę z ćwiczeń. Gwarantujemy następujące progi: Możliwym jest, że zadania okażą się za trudne i te progi zostaną obniżone, jednak gwarantujemy, że ich nie podwyższymy.
  10. Na egzaminie ustnym można zmodyfikować ocenę z ćwiczeń o jedną z wartości -1, -0.5, 0, +0.5, +1.0, +1.5. Nieprzyjście na egzamin ustny skutkuje -1. Ocena mniejsza niż 3 po egzaminie ustnym traktowana jest jako 2. Ocena większa niż 5 po egzaminie ustnym traktowana jest jako 5.
  11. Egzamin ustny będzie wyglądał następująco. Opublikuję listę tematów z wykładu, podzieloną na trzy działy:
    1. teoria minorów,
    2. kolorowania,
    3. ekspandery.
    Na egzaminie ustnym trzeba wybrać jeden z działów 1, 2, 3 jako swój ulubiony. Trzeba będzie mieć zgrubne pojęcie o całym materiale oraz bardzo dokładne pojęcie o ulubionym dziale. Na egzaminie ustnym będzie się losować trzy pytania: po jednym z każdego działu, przy czym oczekujemy bardzo dokładnej odpowiedzi na pytanie z ulubionego działu. Lista tematów z danego działu pojawiać się będzie maksymalnie tydzień po ostatnim wykładzie z tego działu.
  12. Egzamin w sesji poprawkowej (wrześniowej) będzie składał się z części pisemnej (zadaniowej) i ustnej. Wynik części zadaniowej zastępuje punkty z prac domowych. Egzamin ustny odbywa się na tych samych zasadach, co w sesji czerwcowej. Część pisemna nie jest obowiązkowa: można przyjść poprawić jedynie egzamin ustny, używając oceny z ćwiczeń jako oceny modyfikowanej na egzaminie ustnym.

Plan przedmiotu

Na wykładzie omówimy szereg zagadnień ze współczesnej teorii grafów. Będziemy przedstawiać wyniki teoretyczne, okazjonalnie tylko opisując algorytmy. Wykłady podzielone będą na następujące cztery działy:
  1. Teoria minorów. (4 wykłady, w tym dwa powiększone)
  2. Kolorowania. (2.5 wykładu)
  3. Ekspandery. (5.5 wykładu)
Na przedmiocie będzie wyraźny podział na wykład i ćwiczenia. Dokładniejszy plan wykładów (pewnie będzie się jeszcze trochę zmieniał):
Nr Data Co na wykładzie Co na ćwiczeniach Uwagi
1 22.02 Wstępne definicje teorii minorów: dobry porządek, relacja bycia minorem. Dowód twierdzenia Robertsona-Seymoura dla drzew.
Notatki spisał: Piotr Leszczyński.		 Minory, topologiczne minory. WQO. Wstęp do treewidthu. Opublikowanie 1. serii zadań domowych
2 01.03 (x1.5) Charakteryzacja grafów z dużym treewidth przed ciernie (ang. bramble) i splątania (ang. mesh).
Notatki spisali: część piewsza: Cezary Bartoszuk i część druga: Magdalena Bojarska.		 Treewidth i inne miary szerokości grafu.  
3 08.03 Twierdzenie, że duży treewidth implikuje dużą kratę jako minor. Specjalny przypadek grafów planarnych.
Notatki spisała: Barbara Pilat.		 Treewidth i inne miary szerokości grafu - ciąg dalszy. Opublikowanie 2. serii zadań domowych
4 15.03 (x1.5) Twierdzenia strukturalne grafów o wykluczonym ustalonym (topologicznym) minorze. Szkic dowodu twierdzenia Robertsona-Seymoura.
Notatki prowadzi: Piotr Lewandowski + (wakat).		 Uzupełnianie dowodów z wykładu, być może bidimensionality. Termin oddania 1. serii zadań domowych.
- 22.03 Wykład odwołany.
5 05.04 Grafy doskonałe (ang. perfect graphs). Twierdzenie Lovasza (weak perfect graph theorem). Charakteryzacja grafów doskonałych przez wykluczone indukowane podgrafy. Świat klas grafów i zależności między nimi.
Notatki spisał: Tomasz Kociumaka.		 Grafy doskonałe i inne klasy grafów. Opublikowanie 3. serii zadań domowych
6 19.04 Kolorowania grafów planarnych. Twierdzenie o pięciu barwach, kolorowania listowe grafów planarnych. Twierdzenie o czterech barwach.
Notatki spisał: Krzysztof Węsek.		 Discharging, twierdzenie o czterech barwach. Opublikowanie 4. serii zadań domowych
7 26.04 Wstęp do ekspanderów. Ekspansja krawędziowa, wierzchołkowa. Zależności ekspansji od przerw spektralnych.
Notatki spisał: Przemysław Wenus.		 Algebraiczna teoria grafów. Liczenie ekspansji i własności spektralnych różnych grafów.  
8 10.05 Konstrukcja zygzakowa ekspandera.
Notatki spisał: Krzysztof Gogolewski.		 Ciąg dalszy badania ekspansji i spektrum różnych grafów. Konstrukcja zygzakowa na przykładzie. Opublikowanie 5. serii zadań domowych
9 17.05 Błądzenia losowe. Zastosowania ekspanderów: dowód, że L=SL.
Notatki spisał: Marcin Wrochna.		 Błądzenia losowe. Termin oddania 4. serii zadań domowych.
10 24.05 Zastosowania ekspanderów: twierdzenie PCP, część 1.
Notatki prowadzi: Jarosław Błasiok.		 Zastosowania ekspanderów: test liniowości. Opublikowanie 6. serii zadań domowych.
11 07.06 Zastosowania ekspanderów: twierdzenie PCP, część 2. Zastosowania ekspanderów: lepsze redukcje losowości. Termin oddania 5. serii zadań domowych.

Serie zadań domowych

Zadania domowe należy oddawać mailem do godziny 16:00 odpowiedniego piątku, lub w formie pisemnej przez pierwsze piętnaście minut odpowiednich ćwiczeń.
Plan serii:
Numer Termin opublikowania Termin oddania
Seria 1 22.02 (ćwiczenia 1) 15.03 (ćwiczenia 4)
Seria 2 08.03 (ćwiczenia 3) 12.04 (ćwiczenia 6)
Seria 3 05.04 (ćwiczenia 5) 26.04 (ćwiczenia 8)
Seria 4 19.04 (ćwiczenia 7) 17.05 (ćwiczenia 9)
Seria 5 10.05 (ćwiczenia 8) 07.06 (ćwiczenia 11)
Seria 6 24.05 (ćwiczenia 10) 14.06 (pierwszy tydzień sesji)

Literatura

Poniżej lista kilku książek lub artykułów, które mogą być przydatne.
  1. Reinhard Diestel, Graph Theory, Springer-Verlag 2005. Wersja elektroniczna.
  2. Bela Bollobas, Modern Graph Theory, Springer 1998.
  3. Mike Krebs, Anthony Shaheen, Expander Families and Cayley Graphs: A Beginner's Guide, Oxford University Press, USA, 2011.
  4. Artykuły poglądowe i materiały dydaktyczne dostępne w sieci, między innymi: