Strona główna > Archiwalny program seminarium > 2019/2020
2019/2020
11.03
Zbigniew Lonc
Twierdzenie Dilwortha dla borelowskich zbiorów częściowo uporządkowanych
Twierdzenie Dilwortha dla borelowskich zbiorów częściowo uporządkowanych
Streszczenie:
Słynne twierdzenie Dilwortha mówi, że każdy skończony zbiór szerokości k można rozłożyć na k łańcuchów. Mówimy, że zbiór częściowo uporządkowany jest borelowski, jeśli relacja częściowego porządku w tym zbiorze jest zbiorem borelowskim. Referat dotyczy następujacego problemu: czy prawdą jest, że każdy borelowski zbiór częściowo uporządkowany skończonej szerokości k, daje się rozłożyć na k borelowskich łańcuchów. Udowodnimy, że odpowiedź na to pytanie jest pozytywna dla częściowych porządków dających się zanurzyć w naturalny liniowy porządek zbioru liczb rzeczywistych. Pokażemy także, że borelowska wersja twierdzenia dualnego do twierdzenia Dilwortha jest prawdziwa dla zbiorów częściowo uporządkowanych, których graf porównywalności jest lokalnie przeliczalny.
Słynne twierdzenie Dilwortha mówi, że każdy skończony zbiór szerokości k można rozłożyć na k łańcuchów. Mówimy, że zbiór częściowo uporządkowany jest borelowski, jeśli relacja częściowego porządku w tym zbiorze jest zbiorem borelowskim. Referat dotyczy następujacego problemu: czy prawdą jest, że każdy borelowski zbiór częściowo uporządkowany skończonej szerokości k, daje się rozłożyć na k borelowskich łańcuchów. Udowodnimy, że odpowiedź na to pytanie jest pozytywna dla częściowych porządków dających się zanurzyć w naturalny liniowy porządek zbioru liczb rzeczywistych. Pokażemy także, że borelowska wersja twierdzenia dualnego do twierdzenia Dilwortha jest prawdziwa dla zbiorów częściowo uporządkowanych, których graf porównywalności jest lokalnie przeliczalny.
04.03
seminarium odwołane26.02
Jarek Grytczuk
Kolorowanie większościowe grafów przeliczalnych
Streszczenie:
Wyobraźmy sobie graf z pokolorowanymi wierzchołkami. Niektóre krawędzie mają końce w różnych kolorach, to są krawędzie dobre, a niektóre mają końce w tym samym kolorze, i to są krawędzie złe. W poprawnym kolorowaniu grafu wymagamy aby wszystkie krawędzie były dobre. W kolorowaniu większościowymzadowala nas jeżeli z każdego wierzchołka wychodzi co najmniej tyle dobrych krawędzi co złych.
Każdy skończony graf można pokolorować większościowo używając jedynie dwóch kolorów. Jest to prosty i łatwy do udowodnienia fakt: wystarczy wziąć kolorowanie, w którym całkowita liczba złych krawędzi jest minimalna. Nie wiadomo czy podobne twierdzenie jest prawdziwe dla grafów nieskończonych na przeliczalnym zbiorze wierzchołków. Wiadomo jedynie, że trzy kolory wystarczą dla dowolnego grafu nieskończonego (niekoniecznie przeliczalnego).
Kolorowanie większościowe można rozważać w rozmaitych wariantach, np. listowym, skierowanym, ułamkowym, a nawet Borelowskim. Przedstawię kilka ostatnich wyników i problemów otwartych dotyczących tego zagadnienia.
29.01
seminarium odwołane
22.01
Łukasz Brzozowski
Hipoteza spalania grafów - dowód dla drzew homarów oraz propozycje kierunków badań
Streszczenie:
Hipoteza spalania grafów stanowi ważne pytanie m. in. w dziedzinie rozprzestrzeniania informacji. Na wystąpieniu zostanie zaprezentowany dowód hipotezy spalania drzew - homarów skonstruowany w oparciu o dowód dr. Mariusza Zająca dla drzew - gąsienic. Ponadto krótko scharakteryzowane zostaną wybrane kierunki dalszych badań tego zagadnienia wraz z możliwymi rozwiązaniami algorytmicznymi.
15.01
seminarium odwołane
08.01
seminarium odwołane
18.12
seminarium odwołane
11.12
Adam Tyc (PAN)
Z-orientowane triangulacje powierzchni
Streszczenie:
W referacie będę rozważać zygzaki w triangulacjach powierzchni zamkniętych.
Omówię wynik wiążący pewną klasę triangulacji z zanurzeniami digrafów eulerowskich w powierzchnie.
Następnie przejdę do szerszej klasy triangulacji i przedstawię w jaki sposób,
za pomocą zygzaków, możemy uzyskać rozkład tej powierzchni na składowe trzech rodzajów.
Omówię wynik wiążący pewną klasę triangulacji z zanurzeniami digrafów eulerowskich w powierzchnie.
Następnie przejdę do szerszej klasy triangulacji i przedstawię w jaki sposób,
za pomocą zygzaków, możemy uzyskać rozkład tej powierzchni na składowe trzech rodzajów.
04.12
Marta PiecykFinding list homomorphisms from bounded-treewidth graphs
Streszczenie:
In the list homomorphism problem, the input consists of two graphs G and H, together with a list L(v)⊂V(H) for every vertex v ∈ V(G). The task is to find a homomorphism φ:V(G) → V(H) respecting the lists, that is, we have that φ(v) ∈ L(v) for every v ∈ V(H) and if u and v are adjacent in G, then φ(u) and φ(v) are adjacent in H. If H is a fixed graph, then the problem is denoted by LHOM(H). Feder, Hell, and Huang provided the complexity dichotomy for the problem [Feder, Hell, Huang, JGT 2003].
We explore the complexity of the problem parameterized by the treewidth tw(G) of the input graph G. If a tree decomposition of G of width tw(G) is given in the input, then the problem can be solved in time |V(H)|tw(G) ∙ nO(1) by naive dynamic programming. Our main result completely reveals when and by exactly how much this naive algorithm can be improved. We introduce a simple combinatorial invariant i^*(H), which is based on the existence of certain decompositions and incomparable sets, and show that this number should appear as the base of the exponent in the best possible running time. Specifically, we prove for every graph H, for which LHom(H) is NP-hard:
- If a tree decomposition of width tw(G) is given in the input, then the problem can be solved in time i*(H)tw(G) ∙ nO(1).
- Assuming the Strong Exponential-Time Hypothesis (SETH), the problem cannot be solved in time (i*(H)-ε)tw(G)∙ nO(1) for any ε>0.
Thus by matching upper and lower bounds, our result exactly characterizes for every fixed H the complexity of LHOM(H) parameterized by treewidth.
The results are obtained as a joint work with Karolina Okrasa and Paweł Rzążewski.
We explore the complexity of the problem parameterized by the treewidth tw(G) of the input graph G. If a tree decomposition of G of width tw(G) is given in the input, then the problem can be solved in time |V(H)|tw(G) ∙ nO(1) by naive dynamic programming. Our main result completely reveals when and by exactly how much this naive algorithm can be improved. We introduce a simple combinatorial invariant i^*(H), which is based on the existence of certain decompositions and incomparable sets, and show that this number should appear as the base of the exponent in the best possible running time. Specifically, we prove for every graph H, for which LHom(H) is NP-hard:
- If a tree decomposition of width tw(G) is given in the input, then the problem can be solved in time i*(H)tw(G) ∙ nO(1).
- Assuming the Strong Exponential-Time Hypothesis (SETH), the problem cannot be solved in time (i*(H)-ε)tw(G)∙ nO(1) for any ε>0.
Thus by matching upper and lower bounds, our result exactly characterizes for every fixed H the complexity of LHOM(H) parameterized by treewidth.
The results are obtained as a joint work with Karolina Okrasa and Paweł Rzążewski.
27.11
Magdalena Tyniec-Motyka (Akademii Górniczo-Hutnicza)20.11
Tomasz Krawczyk (Uniwersytet Jagielloński)
Testing isomorphism of circular-arc graphs - Hsu's approach revisited
06.11
seminarium odwołane30.10
Zbigniew LoncO dowodzie hipotezy Chung, Diaconisa i Grahama o cyklu uniwersalnym
Streszczenie:
W 1990 roku Chung, Diaconis i Graham postawili hipotezę, że dla każdego naturalnego k i dostatecznie dużego n istnieje
ciąg cykliczny o wyrazach ze zbioru {1,2,...,n}, w którym każde k kolejne wyrazy są różne i każdy k-elementowy podzbiór
zbioru {1,2,...,n} występuje dokładnie raz jako podciąg kolejnych wyrazów, o ile k i n spełniają pewien oczywisty warunek
konieczny. Ostatnie przełomowe wyniki w teorii konfiguracji kombinatorycznych dostarczyły narzędzi, które pozwoliły
udowodnić tę hipotezę, a nawet pewne dość daleko idące jej uogólnienie. W trakcie referatu przedstawię główne idee, które
doprowadziły do udowodnienia hipotezy Chung, Diaconisa i Grahama.
Referat będzie oparty głównie na pracy S. Glock, F. Joos, D. Kühn, D. Osthus, Euler tours in hypergraphs,
https://arxiv.org/abs/1808.07720
W 1990 roku Chung, Diaconis i Graham postawili hipotezę, że dla każdego naturalnego k i dostatecznie dużego n istnieje
ciąg cykliczny o wyrazach ze zbioru {1,2,...,n}, w którym każde k kolejne wyrazy są różne i każdy k-elementowy podzbiór
zbioru {1,2,...,n} występuje dokładnie raz jako podciąg kolejnych wyrazów, o ile k i n spełniają pewien oczywisty warunek
konieczny. Ostatnie przełomowe wyniki w teorii konfiguracji kombinatorycznych dostarczyły narzędzi, które pozwoliły
udowodnić tę hipotezę, a nawet pewne dość daleko idące jej uogólnienie. W trakcie referatu przedstawię główne idee, które
doprowadziły do udowodnienia hipotezy Chung, Diaconisa i Grahama.
Referat będzie oparty głównie na pracy S. Glock, F. Joos, D. Kühn, D. Osthus, Euler tours in hypergraphs,
https://arxiv.org/abs/1808.07720
23.10
seminarium odwołane16.10
Michał DębskiStreszczenie:
Mówimy, że kolorowanie wierzchołkowe grafu G jest p-scentrowane (ang. p-centered), gdy dla każdego spójnego podgrafu H istnieje kolor występujący dokładnie raz na wierzchołkach H lub na wierzchołkach H występuje więcej niż p kolorów. W szczególności, dla p=1 ta definicja jest tożsama z właściwym kolorowaniem wierzchołków, a dla p=2 z kolorowaniem gwieździstym (ang. star coloring). Przez p-scentrowaną liczbę chromatyczną (ang. p-centered chromatic number) grafu G rozumiemy najmniejszą możliwą liczbę kolorów w p-scentrowanym kolorowaniu G.
W trakcie referatu zarysuję najważniejsze problemy powiązane z tą tematyką i udowodnię, że p-scentrowana liczba chromatyczna grafów o ograniczonym stopniu jest liniowa w zależności od p.
Prezentowany materiał będzie oparty na pracy wpólnej z S. Felsnerem, P. Mickiem i F. Schröderem (https://arxiv.org/pdf/1907.04586.pdf )
W trakcie referatu zarysuję najważniejsze problemy powiązane z tą tematyką i udowodnię, że p-scentrowana liczba chromatyczna grafów o ograniczonym stopniu jest liniowa w zależności od p.
Prezentowany materiał będzie oparty na pracy wpólnej z S. Felsnerem, P. Mickiem i F. Schröderem (https://arxiv.org/pdf/1907.
09.10 (wyjątkowo początek o 10.00)
Stanislav Jendrol'On the Cyclic Coloring Conjecture
02.10
seminarium odwołane