Wybrane zagadnienia teorii grafów

semestr letni 2009/2010

Spis treści

• Aktualności
• Informacje ogólne
• Prowadzący
• Warunki zaliczenia
• Plan przedmiotu
• Serie zadań domowych
• Materiały
• Literatura
• Zapisy na egzanim ustny
• Zapisy na egzanim ustny w sesji poprawkowej

Aktualności

• 2010.06.12. Drobne poprawki do notatek z wykładów ze skojarzeń, głównie do rozkładu Gallai-Edmondsa.
• 2010.06.11. Pojawiły się wątpliwości, więc wyjaśniamy dokładnie formułę egzaminu ustnego: będzie pula pytań z każdego działu, z każdej puli losuje się po pytaniu - czyli odpowiada się na cztery pytania. Pytanie składa się z części podstawowej i zaawansowanej, na część zaawansowaną należy odpowiadać tylko z ulubionego działu. Losowanie jest ze zwracaniem, czyli następna osoba może wylosować to samo pytanie.
• 2010.06.08. Pojawiły się rozwiązania serii 8 Wojciecha Czerwińskiego.
• 2010.06.04. Kilka szczegółów co do oceny egzaminu ustnego:
  1. przypominamy: egzamin ustny modyfikuje ocenę z zadań o -1, -0.5, 0, +0.5, +1 lub +1.5,
  2. rozsądne odpowiedzi na pytania z trzech działów gwarantują nieujemną liczbę punktów,
  3. niepowiedzenie nic lub prawie nic na pytania z jednego działu gwarantuje niedodatnią liczbę punktów,
  4. rozsądne odpowiedzi na pytania z czterech działów (być może z drobnymi usterkami) gwarantują co najmniej +1,
  5. niepowiedzenie nic lub prawie nic na pytania z dwóch działów gwarantuje ujemną liczbę punków i daje duże szanse na -1.
• 2010.06.01. Opublikowanie tematów do egzaminu ustnego z kolorowań. Zmniejszyliśmy też wymagania do wersji zaawansowanej ekspanderów: trzeba umieć dowód L=SL lub kawałki dowodu PCP - do wyboru.
• 2010.05.31. Opublikowanie notatek do wykładu 14 oraz zadań z ćwiczeń 14.
• 2010.05.27. Pojawiły się rozwiązania serii 7 Tomasza Kulczyńskiego.
• 2010.05.24. Otwieramy zapisy na egzamin ustny. Dostępne są następujące terminy: czwartek 17 czerwca od 15:00 do 19:00 i piątek 25 czerwca od 10:00 do 14:00. (jeśli wszystkie terminy się wysycą, to przedłużymy je do odpowiednio 20:00 i 15:00). Planujemy 30 minut na egzaminowanego, czyli należy się zapisywać na godziny podzielne przez 30 minut. Zapisujemy się wysyłając maila do nas obu z preferencjami terminowymi. Sale ogłosimy później. Tutaj można znaleźć aktualny stan zapisów.
• 2010.05.24. Jeśli ktoś chce ostatnią, ósmą, serię zadań domowych oddać na papierze (nie mailem), to należy wrzucić ją do 14:30 (!!!) w poniedziałek 7 czerwca do przegródki Jakuba Wojtaszczyka. Przegródki pracownicze znajdują się przy sekretariatach instytutów, na piętrze z pokojami 4xxx. Uwaga! Jakub Wojtaszczyk to nie Przemysław Wojtaszczyk, proszę nie pomylić przegródek.
• 2010.05.23. Opublikowanie notatek do wykładu 13 oraz zadań z ćwiczeń 13.
• 2010.05.18. Pojawiły się rozwiązania serii 5 Marcina Andrychowicza i rozwiązania serii 6 Marka Cygana.
• 2010.05.17. Informujemy, że wstępne ustalenia dotyczące egzaminu ustnego brzmią:
  1. Będzie się on odbywał w czwartek 17 czerwca i piątek 25 czerwca. Termin można jeszcze negocjować (prosimy o maila), ale raczej nie chcemy robić więcej niż dwa terminy.
  2. Będzie 30 minut na egzaminowanego i gdzieś na początku czerwca zrobimy zapisy.
• 2010.05.17. Poprawienie planu wykładu: za tydzień grafy doskonałe (wykład i ćwiczenia prowadzi Marcin), za dwa tygodnie twierdzenie o czterech barwach (wykład i ćwiczenia prowadzi Onufry).
• 2010.05.17. Opublikowanie notatek do wykładu 12, zadań z ćwiczeń 12, serii 8 zadań domowych oraz tematów na egzamin ustny z minorów.
• 2010.05.10. Opublikowanie notatek do wykładu 11 oraz zadań z ćwiczeń 11.
• 2010.04.26. Opublikowanie serii 7 zadań domowych, notatek do wykładu 10 oraz zadań z ćwiczeń 10.
• 2010.04.22. Kosmetyczne zmiany w treści zad. 3 z serii 5.
• 2010.04.20. Pojawiły się rozwiązania serii 4 Marka Cygana.
• 2010.04.19. W obliczu naszej niekonsekwencji w sprawdzaniu list, wycofujemy się z wymagania obecności na ćwiczeniach.
• 2010.04.19. Opublikowanie notatek z wykładu 9 i zadań z ćwiczeń 9.
• 2010.04.15. W odpowiedzi na pytania, wyjaśniamy:
  • W zadaniu trzecim z serii 4 przez "multigraf z pętlami" rozumiemy, że graf G może mieć wielokrotne krawędzie i pętle, ale nie musi.
  • W zadaniu pierwszym z serii 5 można dla uproszczenia założyć, że graf G jest prosty.
• 2010.04.13. Opublikowanie tematów na egzamin ustny z ekspanderów.
• 2010.04.11. Pojawiły się rozwiązania serii 3 Piotra Hofmana.
• 2010.04.11. Opublikowanie serii 6 zadań domowych, notatek do wykładu 8: końcówka ekspanderów, notatek do wykładu 8: początek minorów oraz zadań z ćwiczeń 8.
• 2010.04.09. Aktualizacja treści zadań trzecich z serii 4 i serii 5. Dodaliśmy trochę upraszczających założeń, w stylu dodanie przerwy spektralne, czy ostre nierówności w założeniach.
• 2010.03.29. Opublikowanie serii 5 zadań domowych, notatek do wykładu 7 oraz zadań z ćwiczeń 7.
• 2010.03.22. Opublikowanie notatek do wykładu 6 oraz zadań z ćwiczeń 6.
• 2010.03.16. Postanowiliśmy w dziale materiały umieszczać wybrane rozwiązania serii zadań domowych (za przyzwoleniem autorów). Pojawiły się rozwiązania serii 1 Marcina Andrychowicza oraz rozwiązania serii 2 Jakuba Łąckiego.
• 2010.03.15. Opublikowanie notatek do wykładu 5 oraz zadań z ćwiczeń 5.
• 2010.03.15. Opublikowanie serii 4 zadań domowych.
• 2010.03.13. Wprowadziliśmy nową ocenę: za 130 pkt można dostać ocenę 5.5 z ćwiczeń.
• 2010.03.12. Opublikowanie nowego planu wykładów, ćwiczeń i serii zadań domowych.
• 2010.03.11. W odpowiedzi na powtarzające się maile, informujemy, że w rozwiązaniach prac domowych można używać dowolnych faktów poznanych na wykładzie i ćwiczeniach, nawet jeśli nie dowodziliśmy ich.
• 2010.03.09. Opublikowanie tematów ze skojarzeń na egzamin ustny.
• 2010.03.08. Zgodnie z dzisiejszymi ustaleniami z wykładu, ekspandery i minory poszerzą się o około pół wykładu, a z kolorowań wyleci tw. Grotscha lub tw. Hajnala-Szemeredi. W ciągu tego tygodnia opublikujemy nową siatkę wykładów i trochę zmienioną siatkę serii zadań domowych.
• 2010.03.08. Opublikowanie notatek do wykładu 4 oraz zadań z ćwiczeń 4.
• 2010.03.03. W USOSie osoby zarejestrowane mogą już zobaczyć wyniki serii 1. Do kilku osób wysłaliśmy maile z komentarzami do ocen, jeśli było o czym pisać. O pracach można z nami pogadać w przerwie między wykładem a ćwiczeniami. Wtedy też osoby niezarejestrowane mogą zobaczyć swoje punkty. Jakby ktoś z niezerejestrowanych był niecierpliwy i chciał poznać je wcześniej, prosimy o maila.
• 2010.03.02. Opublikowanie zadań z ćwiczeń 3 oraz krótkiego przypomnienia z algebry liniowej przed ekspanderami.
• 2010.03.02. W ramach dostosowywania materiału do rzeczywistości po doświadczeniach pierwszych trzech wykładów, chcieliśmy wywalić materiał jednego wykładu z programu. Po prostu się nie zmieści, a rozluźnienie planu zwiększy zrozumiałość wykładu. Poniżej zamieszczamy kilka propozycji, co może wylecieć. Do najbliższego wykładu (8 marca) zbieramy opinie - mailem, oraz na samym wykładzie 8 marca. Oto propozycje:
  1. Rezygnujemy z wykładu 7 (zastosowania ekspanderów: twierdzenie PCP), w zamian pół wykładu dostają ekspandery i pół wykładu minory.
  2. Rezygnujemy z połowy wykładu 10 (szkic dowodu twierdzenia Robertsona-Seymoura) oraz z części wykładu 11 (konstrukcja grafów o dużej liczbie chromatycznej), w zamian po pół wykładu dostają ekspandery, a minory zajmują tyle ile zajmowały.
  3. Wykład 11 i 12 się kompresują, kosztem twierdzenia Hajnala-Szemerediego oraz konstrukcji grafów o dużej liczbie chromatycznej. W zamian pół wykładu dostają ekspandery i minory.
  4. Rezygnujemy z wykładu 14 (szkic dowodu twierdzenia o czterech barwach), w zamian po pół wykładu dostają ekspandery i minory.
  5. Rezygnujemy z wykładu 13 (twierdzenie Grotscha), w zamian pół wykładu dostają ekspandery i minory.
• 2010.03.01. Opublikowanie serii 3 zadań domowych oraz notatek do trzeciego wykładu.
• 2010.02.23. Uzupełnienie dowodu charakteryzacji PMP w notatkach do drugiego wykładu oraz naprawienie treści zadania 19 z drugich ćwiczeń.
• 2010.02.22. Opublikowanie zadań na ćwiczenia 2 oraz notatek do drugiego wykładu.
• 2010.02.14. Opublikowanie serii 1 i serii 2 zadań domowych, zadań na ćwiczenia 1 oraz notatek do pierwszego wykładu.

Informacje ogólne

Prowadzący

Warunki zaliczenia

1. Podstawą zaliczenia są zadania domowe, obecność na ćwiczeniach i egzamin ustny.
2. W trakcie semestru będzie osiem 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 obu prowadzących.
4. Każde rozwiązanie oceniane jest jak na Olimpiadzie Matematycznej, tj może dostać 0, 2, 5 lub 6 pkt.
   • 6 pkt, jeśli jest w pełni poprawne
   • 5 pkt, jeśli ma drobne usterki, ale ogólnie jest OK
   • 2 pkt, jeśli jest rozwiązane przynajmniej w połowie
   • 0 pkt w pozostałych przypadkach
5. Na koniec semestru, na podstawie liczby punktów przynajemy ocenę z ćwiczeń. Gwarantujemy następujące progi:
   • 0 pkt daje ocenę 2,
   • 25 pkt daje ocenę 2.5,
   • 40 pkt daje ocenę 3,
   • 55 pkt daje ocenę 3.5,
   • 70 pkt daje ocenę 4,
   • 85 pkt daje ocenę 4.5,
   • 100 pkt daje ocenę 5,
   • 130 pkt daje ocenę 5.5.
   Możliwym jest, że zadania okażą się za trudne i te progi zostaną obniżone, jednak gwarantujemy, że ich nie podwyższymy.
6. 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.
7. Egzamin ustny będzie wyglądał następująco. Opublikujemy listę tematów z wykładu, podzieloną na cztery działy:
   1. skojarzenia,
   2. ekspandery,
   3. szerokości (treewidth i inne) i teoria minorów,
   4. kolorowania.
   Na egzaminie ustnym trzeba wybrać jeden z działów 1, 2, 3, 4 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ć cztery 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.
8. Egzamin w sesji poprawkowej (wrześniowej) będzie składał się z części pisemnej (zadaniowej) i ustnej. Wynik części zadaniowej, który jest oceną, zastępuje ocenę z ćwiczeń. 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.
9. W przypadku niezaliczenia ćwiczeń przez obecności, studentowi przysługuje tylko egzamin poprawkowy (w sesji wrześniowej).

Plan przedmiotu

1. Skojarzenia. (3 wykłady)
2. Ekspandery. (4 wykłady)
3. Teoria minorów i szerokości (treewidth i inne). (3 wykłady)
4. Kolorowania. (4 wykłady)

Serie zadań domowych

Materiały

• Zadania omawiane na ćwiczeniach.
• Nasze notatki do wykładów. To są notatki, które robimy sobie szykując się do wykładów. Będziemy je regularnie publikować, może komuś pomogą, ale nie dajemy żadnych gwarancji na jakość tychże notatek. Wykłady ze skojarzeń. Wykłady z ekspanderów. Wykłady z minorów. Wykłady z kolorowań.
• Przypomnienie algebry liniowej przed wykładami z ekspanderów.
• Tematy na egzamin ustny.
• Wybrane rozwiązania studentów serii zadań domowych:
  • Rozwiązania serii 1 Marcina Andrychowicza.
  • Rozwiązania serii 2 Jakuba Łąckiego.
  • Rozwiązania serii 3 Piotra Hofmana.
  • Rozwiązania serii 4 Marka Cygana.
  • Rozwiązania serii 5 Marcina Andrychowicza.
  • Rozwiązania serii 6 Marka Cygana.
  • Rozwiązania serii 7 Tomasza Kulczyńskiego.
  • Rozwiązania serii 8 Wojciecha Czerwińskiego.

Literatura

1. Reinhard Diestel, Graph Theory, Springer-Verlag 2005. Wersja elektroniczna.
2. Laszlo Lovasz, M.D. Plummer, Matching Theory, AMS Chelsea Publishing, 2009. (istnieje też wydaje z lat 70., ale praktycznie nie do dostania)
3. Bela Bollobas, Modern Graph Theory, Springer 1998.
4. Artykuły poglądowe i materiały dydaktyczne dostępne w sieci, między innymi:
   • Douglas B. West, Ore, Berge-Tutte and Gallai-Edmonds. PS
   • Santosh Vempala, The Matching Polytope: General graphs. PDF
   • Shlomo Hoory, Nathan Linial, Avi Wigderson, Expander Graphs and Their Applications, Bulletin of AMS 2006. PDF
   • Michael A. Nielsen, Introduction to Expander Graphs, 2005. PDF
   • Omer Reingold, Salil Vadhan, and Avi Wigderson, Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors, 2001. PS
   • Laszlo Lovasz, Graph Minor Theory, Bulletin of AMS 2005. PDF
   • Petr Hlineny, Discharging Technique in Practice. PS

Zapisy na egzamin ustny

Zapisy na egzamin ustny w sesji poprawkowej