• skrypt, [pdf] (ostatnia aktualizacja: 1 marca 2024)
• 8 marca, ćwiczenia, Minory, dobre quasi-porządki i szerokość drzewiasta [pdf]
• zestaw zadań I, [pdf], termin: 21 marca 23:59
• 11 marca, ćwiczenia, Szerokość drzewiasta i aspety algorytmiczne [pdf]
• 18 marca, ćwiczenia, Parametry związane z szerokością drzewiastą i zadania zaległe [pdf]
• 25 marca, ćwiczenia, Parametry związane z szerokością drzewiastą i splątania [pdf]
• zestaw zadań II, [pdf], termin: 11 kwietnia 23:59

Podczas kursu poznamy wybrane zagadnienia z teorii minorów w grafach. Teoria ta powstała mimochodem podczas prac nad dowodem jednego z najważniejszych twierdzeń w teorii grafów, to jest twierdzenia Robertsona-Seymoura: W dowolnym nieskończonym zbiorze skończonych grafów istnieją dwa takie, że jeden jest minorem drugiego. Robertson i Seymour, w latach 1983-2012, opublikowali serię manuskryptów budującą teorię i układającą dowód tego twierdzenia (ponad 20 prac, sumarycznie około 750 stron). Sama teoria minorów w grafach znalazła sporo zastosowań i jest aktualnym tematem badawczym w kombinatoryce i informatyce teoretycznej. W ramach kursu:

• poznamy wypowiedź strukturalnego twierdzenia o grafach; zobaczymy też jego kombinatoryczne i algorytmiczne konsekwencje;
• dogłębnie zrozumiemy szerokość drzewiastą (ang. treewidth) grafu jako miarę jego złożoności; zobaczymy wiele powiązanych z nią pojęć takich jak jeżyny (ang. brambles), splątania (ang. tangles); udowodnimy twierdzenie o kracie wskazujące certyfikat na dużą szerokość drzewiastą grafu; poznamy algorytmiczne zastosowania twierdzenia o kracie;
• ułożymy sobie dobrze topologiczne pojęcie powierzchni; poznamy techniki podnoszenia dowodów z płaszczyzny na powierzchnie o większym genusie;
• poznamy własność Erdősa-Pósy i kilka klasycznych (i eleganckich) technik dowodowych w tym nurcie badań;
• w końcu, zobaczymy nowe twierdzenie o strukturze produktowej grafów planarnych i nie tylko; zobaczymy zaskakująco proste zastosowania tego twierdzenia rozwiązujące hipotezy otwarte od wielu dekad.

• 26.II, Wprowadzenie do minorów (rozdział 1)
• 1.III, Jakościowe twierdzenia strukturalne (rozdział 2); Gęstość i liczba chromatyczna grafów z wykluczonym minorem (rozdział 3; do wymuszenia minoru topologicznego)
• ...
• 12.IV, twierdzenie Erdősa-Pósy dla cyklów, twierdzenie Gallai o A-ścieżkach, twierdzenie Tutte'a (charakteryzacja grafów o doskonałych skojarzeniach), formuła Tutte'a-Berge'a, konstrukcja Gallai
• 14.IV, twierdzenie o kracie (nagranie 55' [mp4])

• na kolokwium (pod koniec semestru) można zdobyć 40 punktów
• za rozwiązywanie zadań domowych można zdobyć 60 punktów

Zadania domowe. W trakcie kursu będą publikowane zestawy zadań domowych. Liczba zestawów będzie równa $Z\in\{6,7\}$. Zestawy będą ukazywać się mniej więcej co dwa tygodnie. Rozwiązania zadań studenci przekazują w formie pisemnej prowadzącemu w wyznaczonych terminach. Za rozwiązanie zadań pojedynczego zestawu będzie można uzyskać co najwyżej $X=\frac{60}{Z}$ punktów. Zadania w pojedynczym zestawie będą miały zróżnicowany poziom trudności i zazwyczaj będą tak samo punktowane, a suma punktów za zadania w pojedynczym zestawie będzie zazwyczaj równa $\frac{12}{10} \cdot X$. Zadania można rozwiązywać samodzielnie lub w parze, przy czym każda dwójka studentów może rozwiązywać wspólnie co najwyżej jeden zestaw.

Kodeks honorowy. Studenci nie mogą wyszukiwać, rozwiązań czy wskazówek do zadań domowych w internecie, książkach, pracach naukowych, czy też dyskutować zadania z osobami trzecimi. W sytuacjach wątpliwych najlepiej spytać. Każde rozwiązanie powinno zawierać oświadczenie o samodzielności wykonania (indywidualnie lub w parze).

Ćwiczenia. W ramach ćwiczeń będziemy wspólnie rozwiązywać zadania. Zestawy zadań na ćwiczenia będą publikowane z niewielkim wyprzedzeniem lub rozdawane podczas zajęć. Studenci nie będą ewaluowani za pracę podczas ćwiczeń, a więc w ramach ćwiczeń nie będą przyznawane punkty. Czasami podczas ćwiczeń będziemy kontynuować wykład.

• 5,0 -- $(90,100]$
• 4,5 -- $(80,90]$
• 4,0 -- $(70,80]$
• 3,5 -- $(60,70]$
• 3,0 -- $(50,60]$
• 2,0 -- $(25,50]$
• NZAL -- $[0,25]$

Studenci, którzy otrzymają ocenę co najmniej 3,0 z ćwiczeń przystąpią do egzaminu końcowego w pierwszym terminie w formie ustnej. Studenci, którzy otrzymają ocenę co najmniej 3,0 z egzaminu w pierwszym terminie otrzymają ocenę końcową z kursu równą średniej arytmetycznej ocen z ćwiczeń i egzaminu. Studenci, którzy otrzymali ocenę 2,0 lub NZAL z egzaminu w pierwszym terminie mogą przystąpić do egzaminu w drugim terminie w sesji poprawkowej. Studenci, którzy otrzymali ocenę 2,0 lub NZAL z ćwiczeń nie zaliczą kursu.

• Marcin Briański (2018)
• Andrzej Dorobisz (2018)
• Grzegorz Guśpiel (2018)
• Krzysztof Maziarz (2018)
• Rafał Byczek (2020)
• Jan Derbisz (2020)
• Jędrzej Hodor (2020)
• Piotr Mikołajczyk (2020)