Strona główna > Archiwalny program seminarium > 2017/2018
2017/2018
13.06
Tom Trotter (Georgia Institute of Technology)Fractional Local Dimension
Streszczenie:
The original notion of dimension for posets was introduced by Dushnik and Miller in 1941 and has been studied extensively in the literature. In 1992, Brightwell and Scheinerman developed the notion of fractional dimension as the natural linear programming relaxation of the Dushnik-Miller concept. In this paper, we introduce and study a new parameter for posets we call fractional local dimension. As suggested by the terminology, our parameter is a common generalization of fractional dimension and local dimension.
For a pair (n,d) with 2≤ d<n, we consider the poset P(1,d;n) consisting of all 1-element and d-element subsets of {1,2,...,n} partially ordered by inclusion. This poset has fractional dimension d+1, but for fixed d≥2, its local dimension goes to infinity with n. On the other hand, we show that as n tends to infinity, the fractional dimension of P(1,d;n) tends to a value f(d) which asymptotically satisfiesf(d)=d/(log d-loglog d-o(1)). However, for all d≥2, we will be able to determine f(d) exactly. As an immediate corollary, we show that if P is a poset and d is the maximum degree of a vertex in the comparability graph of P, then the fractional local dimension of P, is at most 2+f(d).
Our arguments use both discrete and continuous methods.
06.06
Karolina OkrasaZłożoność H-kolorowania pewnych klas grafów
Streszczenie:
Podczas referatu opowiem o tym, jak szybko umiemy dla ustalonego grafu H znajdować homomorfizm z grafu G w H, jeśli G jest grafem przecięć dowolnych krzywych lub grafem bez długich indukowanych ścieżek. Jeśli w H nie ma żadnej pary wierzchołków, które mają dwóch wspólnych sąsiadów, istnieje algorytm, oparty na dekompozycji drzewowej grafu G, który dla grafów przecięć krzywych działa w czasie O(n2/3), natomiast dla grafów bez ścieżek długości t w czasie O( √nt) H.
Referat jest oparty na pracy https://arxiv.org/abs/1803.05396
Referat jest oparty na pracy https://arxiv.org/abs/1803.05396
30.05
Krzysztof Węsek
O dolnych ograniczeniach na kolorowanie płaszczyzny
Streszczenie:
Klasyczny problem Hadwigera-Nelsona dotyczy następującego pytania: Jaka
jest najmniejsza liczba kolorów potrzebna do pokolorowania płaszczyzny tak, aby dowolne
dwa punkty w odległości 1 miały różne kolory? Przez ponad 60 lat wiadomo
było jedynie, że odpowiedź leży między 4 i 7. W jednym z głośnych wyników
ostatnich miesięcy Aubrey de Grey dokonał przełomu poprawiając dolne
ograniczenie na 5, ale pytanie jest wciąż szeroko otwarte.
W tym referacie skupię się na uogólnieniu problemu Hadwigera-Nelsona, w
którym ten sam kolor nie może być użyty w punktach w odległości z
przedziału [a,b]. Okazuje się, że dla pewnych przedziałów potrafimy
dokładnie wyznaczyć minimalną liczbę kolorów. Pokażę też nieznany szerzej
dowód, że jeśli a<b, to niezbędne jest co najmniej 6 kolorów.
jest najmniejsza liczba kolorów potrzebna do pokolorowania płaszczyzny tak, aby dowolne
dwa punkty w odległości 1 miały różne kolory? Przez ponad 60 lat wiadomo
było jedynie, że odpowiedź leży między 4 i 7. W jednym z głośnych wyników
ostatnich miesięcy Aubrey de Grey dokonał przełomu poprawiając dolne
ograniczenie na 5, ale pytanie jest wciąż szeroko otwarte.
W tym referacie skupię się na uogólnieniu problemu Hadwigera-Nelsona, w
którym ten sam kolor nie może być użyty w punktach w odległości z
przedziału [a,b]. Okazuje się, że dla pewnych przedziałów potrafimy
dokładnie wyznaczyć minimalną liczbę kolorów. Pokażę też nieznany szerzej
dowód, że jeśli a<b, to niezbędne jest co najmniej 6 kolorów.
Wyniki uzyskane wspólnie z Konstantym Junosza-Szaniawskim.
23.05
Adam Burchardt (Uniwersytet Adama Mickiewicza)O hipotezach Gouldena i Jacksona
Streszczenie:
W 1996 r. Goulden i Jackson wprowadzili rodzinę współczynników μ,νλ) indeksowaną trójkami partycji, która pojawia się w rozwinięciu w szereg potęgowy pewnej sumy Cauchy'ego symetrycznych wielomianów Jacka (α)ϖ. Goulden i Jackson przypuszczali, że za współczynnikami μ,νλ ukryta jest kombinatoryka związana ze skojarzeniami. Postawiona przez nich hipoteza ,,O Skojarzeniach Jacka'' pozostaje do dzisiaj otwarta. Charaktery Jacka są uogólnieniem charakterów grup symetrycznych oraz obiektami dualnymi do wielomianów Jacka. Badamy stałe strukturalne μ,νλ charakterów Jacka. Są one uogólnieniem stałych strukturalnych grup symetrycznych. Podajemy wzory na współczynniki najwyższych stopni wielomianów μ,νλ i μ,νλ. Prezentujemy te rezultaty w kontekście hipotezy ,,O Skojarzeniach Jacka''.
09.05
Paweł Prałat (Ryerson University)Graph Searching Games and Probabilistic Methods
Streszczenie:
The application of probabilistic methods to graph searching problems such as the game of Cops and Robbers and Firefighting is a new topic within graph theory. Research on this topic emerged only over the last few years, and as such, it represents a rapidly evolving and dynamic area. Probability enters the picture in three different ways: 1) graph searching games can be played on random graphs; 2) one of the players can make random moves; 3) probabilistic methods can be used to prove results about deterministic games. During the talk, I will show a few examples from each class.
25.04
Jakub Przybyło (AGH)O pewnych problemach kombinatoryki
Streszczenie:
Seminarium będzie miało formę sesji problemów otwartych, która może przeistoczyć się w szaleńczą dyskusję, przekraczającą ramy czasowe, a nawet obyczajowe.
18.04
Paweł RzążewskiGrafy przecięć dysków i największe kliki
Streszczenie: W roku 1990 Clark, Colbourn i Johnson zaprezentowali wielomianowy algorytm do znajdowania największej kliki w grafach przecięć dysków jednostkowych. Oczywistym kolejnym krokiem było pytanie o złożoność obliczeniową problemu w grafach przecięć dowolnych dysków. Pytanie to było wielokrotnie podnoszone, jednak odpowiedź na nie nadal pozostaje nieznana. W referacie przedstawię nowe wyniki strukturalne dotyczące grafów przecięć dysków. Pozwoliły one na skonstruowanie quasiwielomianowego schematu aproksymacyjnego (QPTAS) oraz algorytmu dokładnego dla problemu największej kliki w grafach przecięć dysków. Wyniki są owocem współpracy zespołowej w składzie: E. Bonnet, P. Giannopoulos, E.-J. Kim, F. Sikora oraz PRz, praca dostępna jest pod adresem https://arxiv.org/abs/1712.05010.
11.04
Joanna SokółKolorowania online dysków i wielokątów o różnych rozmiarach
Streszczenie:
Opowiem dlaczego FirstFit nieźle koloruje dyski różnych rozmiarów. Przedstawię metodę kolorowania online wypukłych figur geometrycznych opartą na ładnych kolorowaniach płaszczyzny. Pokażę też prostą sztuczkę pozwalającą uzyskać kolorowanie online z O(log(σ)) kolorów dla jednokładnych figur o ilorazie rozmiarów σ (dozwalamy przesuwanie i skalowanie, ale nie obracanie). Przestawiane wyniki zostały otrzymane we współpracy z Konstantym Junosza-Szaniawskim oraz Patrykiem Mikosem.
04.04
Jarosław GrytczukMisiowa liczba chromatyczna grafów
Streszczenie:
W każdym wierzchołku grafu G siedzi Miś. Widzi on jedynie te Misie, które siedzą w wierzchołkach sąsiednich. W pewnym momencie Demon zrzuca na głowy misiów kolorowe kapelusze. Każdy Miś próbuje zgadnąć kolor swojego kapelusza. Jeżeli choć jednemu to się uda, to Misie wygrywają z Demonem. Demon wygrywa, jeżeli żaden Miś nie odgadł poprawnie koloru swojego kapelusza. Największa liczba kolorów kapeluszy, przy której Misie mają strategię wygrywającą to właśnie misiowa liczba chromatyczna grafu. Przypomnę co wiemy, a czego nie wiemy o tym zagadkowym parametrze. Nie wiemy, na przykład, czy liczba misiowa grafów planarnych jest ograniczona. Przedstawię dowód, że nie przekracza ona 6 jeżeli graf planarny ma obwód co najmniej 14.
28.03
Paweł Rzążewski
Grafy planarne o zadanych polach ścian, ∃ℝ i ∀∃ℝ
Streszczenie:
Graf płaski G nazywamy uniwersalnym ze względu na pola, jeśli dla każdego przypisania dodatnich pól ścianom tego grafu istnieje równoważny rysunek grafu G realizujący to przypisanie pól. Przedstawię kilka znanych wyników na temat takich grafów, ale temat ten będzie jedynie pretekstem, żeby przedstawić klasę złożoności ∃ℝ, która jest rzeczywistym (w sensie, dotyczącym liczb rzeczywistych) odpowiednikiem klasy NP.
Pokażę przykłady bardzo naturalnych problemów geometrycznych, które okazują się zupełne dla klasy ∃ℝ, co pokazuje ich głębokie związki z algebrą liczb rzeczywistych.
Pokażę przykłady bardzo naturalnych problemów geometrycznych, które okazują się zupełne dla klasy ∃ℝ, co pokazuje ich głębokie związki z algebrą liczb rzeczywistych.
Część referatu będzie oparta na wynikach, uzyskanych razem z Michaelem Dobbinsem, Lindą Kleist i Tillem Miltzowem (https://arxiv.org/abs/1712.05142).
21.03
Izolda Gorgol (Politechnika Lubelska)
Liczba Ramseya - wersja indukowana
Streszczenie:
Przedstawię zagadnienie indukowanej liczby Ramseya, a w szczególności
opowiem o trudnościach z ograniczeniem dolnym, jak również o
(nieprawdziwej) hipotezie dotyczącej indukowanej liczby Ramseya dla
wielokrotnych kopii grafów. Co wiadomo, a co chciałoby się wiedzieć. I
dlaczego stwierdzenie nieprawdziwości hipotezy nie zamyka tematu.
Część wyników jest wspólna z Marią Axenovich z Karlsruhe Institute of
Technology.
opowiem o trudnościach z ograniczeniem dolnym, jak również o
(nieprawdziwej) hipotezie dotyczącej indukowanej liczby Ramseya dla
wielokrotnych kopii grafów. Co wiadomo, a co chciałoby się wiedzieć. I
dlaczego stwierdzenie nieprawdziwości hipotezy nie zamyka tematu.
Część wyników jest wspólna z Marią Axenovich z Karlsruhe Institute of
Technology.
14.03
Jarosław GrytczukO pewnym problemie Erdősa
Streszczenie:
W nawiązaniu do słynnego problemu Grahama-Newmana, Erdős zapytał: czy dla każdego k istnieje zbiór punktów na płaszczyźnie taki, że w dowolnym dwukolorowaniu tego zbioru pojawi się monochromatyczna prosta zawierająca co najmniej k punktów? Problem rozwiązał pozytywnie Andrzej Kurek około 20 lat temu, ale dowód nigdy nie został opublikowany. Przedstawię ten dowód. Naszkicuję także nowy kontekst tego zagadnienia związany z kolorowaniem grafów geometrycznych.
07.03
Jerzy Konarski (Akademia Górniczo-Hutnicza)(Niemal) pakowania (hiper)grafów
Streszczenie:
Od lat matematycy głowią się nad problemem sprawdzenia jak dużo krawędzi musi dowolny graf posiadać, aby na pewno zawierać kopię innego, ale danego grafu. A gdyby tak oba grafy ukryć przed wścibskim wzrokiem i umysłem matematyka? Pakowanie grafów idzie właśnie o ten jeden krok dalej - jak duże mogą być dwa dowolne grafy, aby zawsze dało się znaleźć kopię jednego w dopełnieniu drugiego. Innymi słowy, aby dało się je zdefiniować na tym samym zbiorze wierzchołków tak, aby krawędzie się nie powtórzyły. W tym temacie dużo zostało już udowodnione od późnych lat 70. ubiegłego wieku. W moim referacie pokażę co udało się pokazać w przypadku niemal pakowania grafów (w którym pewne krawędzie jednak mogą się pokrywać) oraz jak sprawa wygląda w przypadku hipergrafów.
28.02 seminarium łączone z Seminarium Probabilistycznym, dlatego odbędzie się w sali 314
Alexandru Nica (University of Waterloo)Free probabilistic aspects of meandric systems
Streszczenie:
I will consider a family of diagrammatic objects (well-known to mathematical
physicists and to combinatorialists) which go under the name of "meandric
systems". I will explain how meandric systems arise in calculations done
in a non-commutative probability framework, and I will show how tools from
free probability can be used to study some aspects of the asymptotic behaviour
of a random meandric system of large order. The talk is based on a joint
work with Ian Goulden and Doron Puder (arXiv:1708.05188) and on a joint work
with Ping Zhong (arXiv:1801.05501).
21.02
Mariusz ZającInne spojrzenie na planarność grafów
Streszczenie:
Ostatnio było zapotrzebowanie na grafy planarne (np. dlaczego można przyjąć, że krawędzie są łamanymi i nie martwić się krzywą Peano),
w tym wyjaśnienie, dlaczego naprawdę K3,3 i K5 (w tej właśnie nieprzypadkowej kolejności) nie są planarne. Dowód tw. Kuratowskiego
byłby przy okazji. Nie mój, ale inny niż w książkach i poniekąd słuszniejszy.
24.01
Jarosław GrytczukProblem samotnego biegacza
Streszczenie:
Dokoła stadionu o obwodzie jednostkowym biegnie N biegaczy, każdy ze stałą, ale inną prędkością. Jest głucha noc, ciemno choć oko wykol. Każdy biegacz ma na głowie lampkę, która oświetla łuk długości 1/N. Jeżeli w pewnej chwili biegacz nie widzi przed sobą żadnego innego biegacza, ani żaden inny biegacz nie oświetla go z tyłu - czuje się on samotny. Złowieszcza hipoteza głosi, że każdy biegacz odczuje kiedyś dojmującą samotność. Opowiem co wiemy, a czego nie wiemy o tej hipotezie.
17.01
Urszula PastwaStreszczenie:
Uogólnimy część wyników z pracy "Grasshopper avoidance of patterns" (M. Dębski, U. Pastwa, K. Węsek) na przypadek, w którym dopuszczamy przeskoki dłuższe niż jeden symbol. Przedstawimy zarówno ograniczenia dolne, jak i górne, na minimalną liczbę symboli potrzebną do uniknięcia repetycji.
10.01
Jarosław GrytczukWariacje na temat twierdzenia Brooksa
Streszczenie:
Przedstawię kilka spośród nieskończenie wielu uogólnień tytułowego twierdzenia. Postawię także kilka pytań otwartych. Na przykład: czy jest prawdziwa pędzelkowa wersja twierdzenia Brooksa dla grafów oznakowanych? Pokażę też nowe narzędzie, które może się przydać nie tylko tu, czyli Lemat Kiersteada-Raberna o pędzlowaniu grafów.
03.01
seminarium odwołane
20.12
Zbigniew LoncO sprawiedliwym podziale dóbr
Streszczenie:
Referat dotyczyć będzie podziałów skończonego zbioru niepodzielnych dóbr pomiędzy pewną liczbę agentów. Każdy z agentów ma swoją
wycenę poszczególnych dóbr, a różni agenci mogą mieć zupełnie różne wyceny. Chodzi o znalezienie podziału zbioru dóbr
tak, aby każdy z agentów był "w miarę" zadowolony, tzn. żeby zbiór dóbr, które dostaje spełniał jego oczekiwania
(odpowiednio zdefiniowane). Referat dotyczyć będzie jednego z nowszych tego typu kryteriów zadowolenia prowadzących do tzw. maksymalnie
minimalnego podziału udziałów, w skrócie MMS-podział (maximin share allocation). Każdy agent x wyobraża sobie następujący
protokół podziału zbioru dóbr pomiędzy n agentów: x dzieli zbiór dóbr na n części, każdy z pozostałych n-1 agentów wybiera którąś
z tych części, a x bierze tę część, która zostanie na samym końcu. Oczywiście agent x dzieli zbiór dóbr tak, żeby dostać jak najwięcej
niezależnie od wyborów innych agentów. Agent x jest zadowolony, jeśli w rzeczywistym podziale dostanie dobra o wartości co najmniej takiej,
jak w tym wyobrażonym protokole. Ten rzeczywisty podział jest MMS-podziałem, jeśli każdy z n agentów jest zadowolony. Przedstawionych
zostanie kilka subiektywnie wybranych wyników w tej dziedzinie o kombinatorycznym charakterze oraz kilka otwartych problemów.
13.12
Marta PrzyborowskaZbiory osobliwe
Streszczenie:
Opowiem o posetach, które napotkaliśmy z prof. A. Rutkowskim badając problem rekonstrukcji posetów wysokości 1 i nazwaliśmy zbiorami osobliwymi.
Niech P będzie posetem wysokości 1 , a P-{a} jego podzbiorem, zwanym kartą, i oznaczanym Pa. Spośród elementów zbioru P wyróżnimy takie, które mają dokładnie jednego sąsiada stopnia 1, dokładnie jednego sąsiada stopnia 2, itd. Takie elementy nazwiemy punktami osobliwymi.
Poset P nazywać będziemy osobliwym, jeśli ma elementy aϵMinP i bϵMaxP, takie że a≠b i Pa jest izomorficzna z Pb. Punkty a,b nazwiemy biegunami. Okazuje się, że bieguny są punktami osobliwymi, a dzięki kilku operacjom na posetach można stworzyć wielką rodzinę zbiorów osobliwych.
06.12
Jarosław GrytczukHipoteza o dwóch znakach i dwóch kolorach (w dwóch odcieniach)
Streszczenie:
Graf oznakowany to zwykły graf, którego każda krawędź została oznakowana plusem lub minusem. Grafy oznakowane kolorujemy liczbami całkowitymi, a kolorowanie jest właściwe jeżeli wynik działania zgodnego ze znakiem krawędzi na jej końcach jest różny od zera. Liczba chromatyczna grafu oznakowanego, to rozmiar najmniejszego zbioru symetrycznego względem zera, którym da się właściwie pokolorować graf. Tytułowa hipoteza mówi, że dla grafów oznakowanych planarnych liczba ta nie przekracza czterech. Pociąga ona inną hipotezę mówiącą, że każdy graf planarny można pokolorować z list czteroelementowych zawierających dwa dowolne kolory w dwóch odcieniach. Przedstawię prosty dowód tej implikacji oraz algebraiczny dowód 5-wybieralności grafów planarnych oznakowanych.
29.11
Mariusz ZającNowy dowód twierdzenia Brooksa
Streszczenie:
Twierdzenie Brooksa mówi, że (poza łatwymi do opisania wyjątkami)
do pokolorowania wierzchołków grafu wystarczy użyć tylu kolorów,
ile wynosi największy stopień jego wierzchołka.
Przedstawię całkowicie elementarny dowód tego faktu, po czym pokażę,
na jakie inne rodzaje kolorowań przenosi się schemat tego dowodu.
do pokolorowania wierzchołków grafu wystarczy użyć tylu kolorów,
ile wynosi największy stopień jego wierzchołka.
Przedstawię całkowicie elementarny dowód tego faktu, po czym pokażę,
na jakie inne rodzaje kolorowań przenosi się schemat tego dowodu.
22.11 (odwołany)
Jarosław GrytczukWszelkie znaki na niebie i ziemi...
Streszczenie:
Przedstawię algebraiczną metodę Alona-Tarsi'ego kolorowania listowego grafów oraz próbę jej uogólnienia na grafy oznakowane. Jeżeli próba powiedzie się, to być może udowodnimy, że grafy planarne-oznakowane są 5-wybieralne (co wiadomo), albo, że grafy planarne-oznakowane-dwudzielne są 3-wybieralne (czego jeszcze nie wiadomo), albo jeszcze coś innego, np. malarską wersję twierdzenia Brooksa dla grafów oznakowanych. Jeżeli próba nie powiedzie się, to dopełnimy obrazu klęski kolejnymi problemami otwartymi z cyklu: czy dla grafów oznakowanych zachodzi twierdzenie o czterech kolorach, twierdzenie Vizinga, twierdzenie "cykl plus trójkąty", itp.
15.11
Grzegorz Gutowski (Uniwersytet Jagielloński)Abstrakt:
Plane Graphs are Facially-non-repetitively C-Choosable
We prove existence of a constant C such that given any planar drawing
of a graph, and a list of C permissible colors for each vertex, there
is a choice of a permissible color for each vertex such that the
sequence of colors of the vertices on any facial simple path is not a
repetition.
Plane Graphs are Facially-non-repetitively C-Choosable
We prove existence of a constant C such that given any planar drawing
of a graph, and a list of C permissible colors for each vertex, there
is a choice of a permissible color for each vertex such that the
sequence of colors of the vertices on any facial simple path is not a
repetition.
08.11
Przemysław Gordinowicz (Politechnika Łódzka)Własność Hrushovskiego dla grafów i hipergrafów k-jednorodnych
Abstrakt:
Twierdzenie Hrushovskiego mówi, że dla dowolnego skończonego grafu X, istnieje jego skończony nadgraf Z taki, że dowolny izomorfizm między indukowanymi podgrafami X rozszerza się do automorfizmu Z. Podczas referatu pokażę elegancki dowód tego twierdzenia pochodzący od C. Millieta, a następnie jego uogólnienie na hipergrafy k-jednorodne, a w konsekwencji na dowolne hipergrafy (znaczące uproszczenie dowodu twierdzenia Herwiga).
25.10
Jacek Wesołowski
Od DAGów do grafów istotnych - markowskie modele graficzne - kontynuacjawspólne spotkanie z Seminarium Probablistycznym, tym samym odbędzie się w sali 317
Abstrakt:
patrz niżej
18.10
Jacek Wesołowski
Od DAGów do grafów istotnych - markowskie modele graficznewspólne spotkanie z Seminarium Probablistycznym, tym samym odbędzie się w sali 317
Abstrakt:
Opowiem o dyskretnych markowskich modelach losowych, w
których markowskość jest definiowana za pomocą DAGu (ang. directed acyclic
graph). Rodzina DAGów równoważna markowsko utożsamiana jest z pewnym
grafem mieszanym (grafem o krawędziach skierowanych bądż nie) zwanym
grafem istotnym. Wiadomo, że równoważność markowska DAGów alternatywnie
opisywana jest za pomocą tzw. niemoralności - pojęcia czysto grafowego.
Ten znany fakt jest podstawą większości wyników, które będę prezentował.
Dlatego spora część wystąpienia będzie dotyczyła bardziej teorii grafów,
mniej probabilistyki.
W referacie: (1) podam nową charakteryzację grafów istotnych; (2) opiszę
kratę grafów quasi-istotnych (grafy te w naturalny sposób "interpolują"
między DAGami a grafami istotnymi); (3) zajmę się własnością markowskości
względem grafów quasi-istotnych; (4) opiszę transformację psi, która
pozwala "poruszać" się od elementu minimalnego do maksymalnego we
wspomnianej kracie; (5) podam nowy algorytm, nazwany CCC, (którego
podstawą jest transformacja psi) prowadzący od DAGu do odpowiadającego mu
grafu istotnego (podam też, uwaga, uwaga: jego implementację w eRze !)
Wszystko z dowodami, przynajmniej taki jest plan.
To efekt wspólnej pracy z Helene Massam (York Univ., Toronto) oraz z
Johnem Noblem (UW, Warszawa)
których markowskość jest definiowana za pomocą DAGu (ang. directed acyclic
graph). Rodzina DAGów równoważna markowsko utożsamiana jest z pewnym
grafem mieszanym (grafem o krawędziach skierowanych bądż nie) zwanym
grafem istotnym. Wiadomo, że równoważność markowska DAGów alternatywnie
opisywana jest za pomocą tzw. niemoralności - pojęcia czysto grafowego.
Ten znany fakt jest podstawą większości wyników, które będę prezentował.
Dlatego spora część wystąpienia będzie dotyczyła bardziej teorii grafów,
mniej probabilistyki.
W referacie: (1) podam nową charakteryzację grafów istotnych; (2) opiszę
kratę grafów quasi-istotnych (grafy te w naturalny sposób "interpolują"
między DAGami a grafami istotnymi); (3) zajmę się własnością markowskości
względem grafów quasi-istotnych; (4) opiszę transformację psi, która
pozwala "poruszać" się od elementu minimalnego do maksymalnego we
wspomnianej kracie; (5) podam nowy algorytm, nazwany CCC, (którego
podstawą jest transformacja psi) prowadzący od DAGu do odpowiadającego mu
grafu istotnego (podam też, uwaga, uwaga: jego implementację w eRze !)
Wszystko z dowodami, przynajmniej taki jest plan.
To efekt wspólnej pracy z Helene Massam (York Univ., Toronto) oraz z
Johnem Noblem (UW, Warszawa)
11.10
Paweł Rzążewski
Listowe homomorfizmy z grafów o ograniczonej szerokości drzewowej w grafy zwrotne: pełna klasyfikacja złożoności.Abstrakt:
In the list homomorphism problem, the input consists of two graphs $G$ and $H$, together with a list $L(v)subseteq V(H)$ for every vertex $vin V(G)$. The task is to find a homomorphism $phi:V(G)to V(H)$ respecting the lists, that is, we have that $phi(v)in L(v)$ for every $vin V(H)$ and if $u$ and $v$ are adjacent in $G$, then $phi(u)$ and $phi(v)$ are adjacent in $H$. If $H$ is a fixed graph, then the problem is denoted LHOM($H$). We consider the reflexive version of the problem, where we assume that every vertex in $H$ has a self-loop. If is known that reflexive LHOM($H$) is polynomial-time solvable if $H$ is an interval graph and it is NP-complete otherwise [Feder and Hell, JCTB 1998].
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)} n^{O(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 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 fixed graph $H$ that
- 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)} n^{O(1)}$.
- Assuming the Strong Exponential-Time Hypothesis (SETH), the probem cannot be solved in time $(i^*(H)-epsilon)^{tw(G)} n^{O(1)}$ for any $epsilon>0$.
Thus by matching upper and lower bounds, our result exactly characterizes for every fixed $H$ the complexity of reflexive LHOM($H$) parameterized by treewidth.
These results are joint work with Laszlo Egri and Daniel Marx.
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)} n^{O(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 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 fixed graph $H$ that
- 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)} n^{O(1)}$.
- Assuming the Strong Exponential-Time Hypothesis (SETH), the probem cannot be solved in time $(i^*(H)-epsilon)^{tw(G)} n^{O(1)}$ for any $epsilon>0$.
Thus by matching upper and lower bounds, our result exactly characterizes for every fixed $H$ the complexity of reflexive LHOM($H$) parameterized by treewidth.
These results are joint work with Laszlo Egri and Daniel Marx.
04.10
spotkanie organizacyjne