Kombinatoryka struktur porządkowych
dla informatyki analitycznej
semestr zimowy 2018/19
Zespół Katedr i Zakładów Informatyki Matematycznej
Wydział Matematyki i Informatyki
Uniwersytet Jagielloński
Prowadzący
Piotr Micek
Zajęcia
wykłady w środy 14:15 - 15:45 w sali 0086
ćwiczenia w środy 10:15 - 11:45 w sali 0122
Lista pytań egzaminacyjnych [
pdf]
Aktualna punktacja
- [pdf] (aktualizacja: 24 stycznia)
Warunki zaliczenia
W trakcie kursu można zdobyć 100 punktów, przy czym:
- na każdym z dwóch kolokwiów można zdobyć 33 punktów
- za aktywność podczas ćwiczeń można zdobyć 34 punktów
Studenci podczas wypełniania listy obecności deklarują możliwość rozwiązania konkretnych zadań z zestawu obowiązującego na danych zajęciach.
Aktywność studenta podczas zajęć oceniana jest na podstawie deklaracji i prezentacji rozwiązanych zadań w skali od 0,0 do 3,0 punktu.
Oceny z ćwiczeń wystawiane będą względem następujących progów:
- 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 ukończą ćwiczenia z oceną 2,0 będą mieli jedną możliwość poprawienia oceny w sesji poprawkowej poprzez napisanie kolokwium z całości materiału.
Ewentualne zaliczenie ćwiczeń w tym trybie będzie z oceną 3,0.
Wszyscy studenci, którzy otrzymali zaliczenie z ćwiczeń (tj. ocenę przynajmniej 3,0) przystąpią do egzaminu końcowego w formie ustnej.
Jeśli student otrzymał co najmniej 3,0 z ćwiczeń i egzaminu to jego ocena końcowa jest średnią arytmetyczną tych dwóch ocen zaokrągloną do góry do najbliższej oceny.
W pozostałych przypadkach student otrzymuje ocenę 2,0 lub NZAL.
Studenci mogą zdobyć dodatkowe punkty za spisanie części notatek do wykładów.
Stub pliku z notatkami jest tutaj.
Publiczne repo z notatkami jest tutaj.
W celu uzyskania prawa do zapisu proszę o kontakt z prowadzącym.
Zestawy zadań
- 10.X., Wymiar i porządki przedziałowe [pdf]
- 17.X., Wymiar i etykietowania triangulacji [pdf]
- 24.X., Wymiar, liczba pudełkowa, kwadrangulacje i trianguacje [pdf]
- 31.X., Wymiar i uogólnione liczby kolorujące [pdf]
- 7.XI., Separujące dekompozycje, pary bliźniaczych drzew binarnych, st-orientacje [pdf]
- 14.XI., Słabe liczby kolorujące: dwa zastosowania [pdf]
- 21.XI., Wymiar posetów planarnych [pdf]
- 28.XI., Wymiar Boolowski [pdf]
- 12.XII., Algorytmy on-line [pdf]
- 19.XII., First-fit i algorytmy on-line [pdf]
- 16.I., Grafy przecięć i rozłączności [pdf]
Wykłady i materiały dodatkowe
- 3.X (dwa wykłady),
trzy definicje wymiaru posetów;
przykłady posetów o dużym wymiarze:
stadardowe przykłady,
posety incydencji,
posety sąsiedztwa,
porządki przedzałowe;
charakteryzacja porządków przedziałowych jako (2+2)-free.
- 10.X,
dim <= width,
Twierdzenie Schnydera
- etykietowania Schnydera: slajdy z wykładu [pdf]
- wykład Toma Trottera o twierdzeniu Schnydera [link] (tam można znaleźć całą serię wykładów)
-
17.X,
Twierdzenie Brightwella-Trottera i dowód Felsnera,
- S. Felsner, The Order Dimension of Planar Maps Revisited [pdf],
SIAM Journal on Discrete Mathematics 28 (2014) 1093-1101
- S. Felsner, E. Fusy, M. Noy, D. Orden, Bijections for Baxter Families and Related Objects [pdf],
Journal of Combinatorial Theory (A) 118 (2011), 993-1020.
-
24.X,
ograniczenie wymiaru dla posetów z zewnętrznie planarnym grafem pokryć,
przykłady Kelly'ego,
wypowiedzi twierdzeń ograniczających wymiar posetów "planarnych" w terminach wysokości,
wprowadzenie do uogólnionych liczb kolorujących
-
7.XI,
uogólnione liczby kolorujące, dwa przykłady zastosowań: "exact-distance colorings", wymiar posetów (patrz Twierdzenie 2)
- J. van den Heuvel, H. Kierstead, D. Quiroz, Chromatic Number of Exact Distance Graphs [arXiv]
- Nowhere dense graph classes and dimension [arXiv]
-
14.XI, (Michał Seweryn)
wielomianowe ograniczenie na wymiar posetów o planarnych grafach pokryć w terminach ich wysokości (i wielkości największego standardowego przykładu);
lemat wykorzystujący liczby kolorujące można znaleźć tutaj: Lemat 7
-
21.XI,
wymiar Boolowski
- J. Nešetřil, P. Pudlák, A Note on Boolean Dimension of Posets [SpringerLink]
- B. Walczak, William T. Trotter, Boolean dimension and local dimension [arXiv]
-
S. Felsner, T. Mészáros, P. Micek, Boolean dimension and tree-width [arXiv]
-
28.XI,
algorytmy on-line
-
B. Bosek, S. Felsner, K. Kloch, T. Krawczyk,
G. Matecki, P. Micek,
On-line Chain Partitions of Orders: A survey
[pdf]
-
12.XII, First-Fit
-
column construction method: oryginalna pracka z dowodem na 10w (trochę czytelniejsza):
[Google Scholar],
pracka z dowodem na 8w (trochę toporniejsza ale dowód jest poprawny) [SpringerLink]
-
19.XII, rozmiar największego podposetu dwudzielnego z pełną lub pustą relacją
-
J. Fox, A Bipartite Analogue of Dilworth’s Theorem [pdf]
-
9.I, (Michał Seweryn) grafy przecięć i rozłączności geometrycznych obiektów na płaszczyźnie
-
przegląd o chi-ograniczonych klasach grafów:
A. Scott, P. Seympur, A survey of chi-boundedness arXiv
-
grafy Burlinga (zwięzła abstrakcyjna definicja):
S. Felsner, G. Joret, P. Micek, W. Trotter, V. Wiechert, Burling graphs, chromatic number, and orthogonal tree-decompositions [arXiv],
- grafy przecięć odcinków na płaszczyźnie:
A. Pawlik i inni, Triangle-free Intersection Graphs of Line Segments with Large Chromatic Number [arXiv]
- ... i innych obiektów wciąż przy pomocy konstrukcji Burlinga:
A. Pawlik i inni, Triangle-free geometric intersection graphs with large chromatic number
[arXiv]
- 16.I, grafy rozłączności rodzin krzywych
-
J. Pach, I. Tomon, On the chromatic number of disjointness graphs of curves arXiv