Ostatnia aktualizacja:
January 16. 2018 17:01:35
Strona główna > Aktualny program seminarium

Aktualny program seminarium

Plan referatów może ulec zmianie. Jeśli chcesz otrzymywać regularnie aktualny plan referatów to napisz do sekretarza seminarium.


17.01
Urszula Pastwa
Unikanie r-repetycji z długimi przeskokami

Streszczenie:
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 Grytczuk
Wariacje 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 Lonc
O 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 Przyborowska
Zbiory 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 nazywać będziemy osobliwym, jeśli ma elementy aϵMinbϵMaxP, takie że ab 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 Grytczuk
Hipoteza 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ąc
Nowy 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.


22.11 (odwołany)
Jarosław Grytczuk
Wszelkie 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)
Plane Graphs Are Facially-non-Repetitively 104 · 107-Choosable

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.


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 - kontynuacja
wspó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 graficzne
wspó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)


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.


04.10 
spotkanie organizacyjne