Strona główna > Archiwalny program seminarium > 2020/2021
2020/2021
16.06
Bartłomiej Bosek
Recoloring Unit Interval Graphs with Limited Recourse Budget
Streszczenie:
We consider the problem of coloring a unit interval graph dynamically. Intervals arrive one after the other and have to be colored immediately such that no two intervals of the same color overlap. In each step, only a limited number of intervals may be recolored to maintain a proper coloring (thus interpolating between the well-studied online and offline settings). The number of allowed recolorings per step is the so-called recourse budget. In addition, I will discuss issues related to the chromatic number of unit circular arc graphs, which are closely related to the above problem.
This isj oint work with Anna Zych-Pawlewicz.
10.06
Mirosław Truszczyński
Fun with the Collatz Conjecture
Streszczenie:
The Collatz conjecture (also known as the 3x+1 or 3n+1 conjecture) is simple to state:
If one starts with any positive integer, and repeatedly computes the next integer by dividing the current one by 2, in the case it is even, or by multiplying it by 3 and adding 1, otherwise, then one will eventually reach 1.
Despite this simple statement accessible to everyone, the Conjecture, now 84 years old, has so far resisted all attempts at proof.
I will not prove it either. I will do something much easier. I will propose a general setting in which the Collatz conjecture is just one of many. Based on extensive computational experimentation, I will show how the new setting offers new insights, suggests intriguing patterns, and brings up new challenging questions, most, I am sure, as difficult to answer as the original one, but some, I hope, perhaps a little easier.
09.06
Adam Tyc
Struktura zygzaków w triangulacjach powierzchni
Streszczenie:
Podczas referatu zaprezentuję wyniki teorii zygzaków dotyczące triangulacji powierzchni. Przykładem jednego z tych wyników jest związek klasy tzw. z-jednorodnych triangulacji z zanurzeniami digrafów eulerowskich w powierzchnie. Przedstawię również topologiczną charakteryzację tej klasy triangulacji i omówię procedurę pozwalającą na uzyskiwanie triangulacji, które są jednocześnie z-zawiązane i z-jednorodne.
02.06
Pavel Dvořák
Bears with Hats and Independence Polynomials
Streszczenie:
Consider the following hat guessing game. A bear sits on each vertex of a graph G, and a demon puts on each bear a hat colored by one of h colors. Each bear sees only the hat colors of his neighbors. Based on this information only, each bear has to guess g colors and he guesses correctly if his hat color is included in his guesses. The bears win if at least one bear guesses correctly for any hat arrangement.
I'll introduce a new parameter - fractional hat chromatic number, arising from the hat guessing game. This parameter generalizes the hat chromatic number which is a parameter studied before.I'll present a surprising connection between the hat guessing game and the independence polynomial of graphs. This connection allows us to compute the fractional hat chromatic number of chordal graphs in polynomial time, to bound fractional hat chromatic number by a function of maximum degree of G, and to compute the exact value of the fractional chromatic number of cliques, paths, and cycles.
This is a joint work with Václav Blažej and Michal Opler.
19.05
Nataliya Petryshyn
Problem istnienia {2K_2,H}-dekompozycji grafów i związek z zakorzenionymi upakowaniami
Streszczenie:
Mówimy, że rodzina podgrafów grafu G jest krawędziowym _H_-upakowaniem w graf G, jeśli grafy w tej rodzinie są krawędziowo rozłączne i każdy graf z rodziny jest izomorficzny z pewnym grafem z rodziny _H_. _H_-dekompozycją grafu G nazywamy krawędziowe _H_-upakowanie w graf G, w którym zbiory krawędzi grafów z upakowania tworzą podział E(G). Problem istnienia _H_-dekompozycji jest następujący:
Problem DEC(_H_)
Dane: Graf G.
Pytanie: Czy G ma _H_-dekompozycję?
Dane: Graf G.
Pytanie: Czy G ma _H_-dekompozycję?
Opowiem o wynikach dotyczących złożoności obliczeniowej problemu istnienia {2K_2,H}-dekompozycji grafu, tj. istnienia krawędziowej dekompozycji na podgrafy izomorficzne z 2K_2 (2 krawędziowe skojarzenie) lub H, gdzie H jest ustalonym grafem.
Między innymi zaprezentuję twierdzenia pokazujące związek pomiędzy problemami istnienia {2K_2,H}-dekompozycji a problemami znalezienia maksymalnych zakorzenionych upakowań, problemami istnienia zakorzenionych dekompozycji i zakorzenionych faktorów. Na mocy tych twierdzeń i wyników dotyczących zakorzenionych upakowań, zakorzenionych dekompozycji i zakorzenionych faktorów dla pewnych dużych klas grafów można pokazać, że problem DEC({2K_2,H}) jest wielomianowy i dla innych klas grafów, że problem DEC({2K_2,H}) jest NP-zupełny.
Zakorzenionym grafem jest para (G,T), gdzie G jest grafem oraz T podzbiorem zbioru wierzchołków grafu G. Dwa zakorzenione grafy (G,T) i (H,S) są izomorficzne jeśli istnieje izomorfizm grafów G i H taki, że S jest obrazem T w tym izomorfizmie. Zakorzeniony graf (H,S) jest zakorzenionym podgrafem zakorzenionego grafu (G,T) jeśli H jest podgrafem G oraz S jest podzbiorem T. Przez zakorzenione (H,S)-upakowanie w zakorzeniony graf (G,T) rozumiemy rodzinę (H_1,S_1),..., (H_p,S_p) zakorzenionych podgrafów (G,T) izomorficznych z (H,S) takich, że zbiory krawędzi E(H_1),...,E(H_p) są parami rozłączne oraz zbiory S_1,..., S_p są parami rozłączne. Takie (H,S)-upakowanie jest zakorzenioną dekompozycją zakorzenionego grafu (G,T) jeśli E(H_1),...,E(H_p) tworzą podział E(G) zaś jest zakorzenionym faktorem w zakorzeniony graf (G,T) jeśli S_1,...,S_p tworzą podział T. Koncepcja zakorzenionego upakowania w zakorzeniony graf jest wspólnym uogólnieniem krawędziowego i wierzchołkowego upakowania w graf.
12.05
Monika Pilśniak
Rozróżniające kolorowania właściwe digrafów symetrycznych
Streszczenie:
Mówimy, że kolorowanie krawędzi grafu jest rozróżniające, jeśli jedynym automorfizmem grafu, zachowującym kolorowanie, jest identyczność. Najmniejszą liczbę kolorów we właściwym kolorowaniu rozróżniającym grafu G nazywamy jego indeksem rozróżniającym. Kalinowski i Pilśniak udowodnili w 2015, że zawsze Delta(G)+1 kolorów wystarczy, by przełamać wszystkie nietrywialne automorfizmy spójnego grafu rzędu co najmniej 7.
Rozważymy różne definicje kolorowania właściwego łuków digrafów symetrycznych. Pokażemy ograniczenia na indeks chromatyczny w każdym przypadku i indeks rozróżniający spójnego digrafu symetrycznego ze względu na stopień maksymalny jego szkieletu, oraz uzasadnimy optymalność uzyskanych ograniczeń.
05.05
Andrzej Żak
Grafy odporne na błędy
Streszczenie:
Będzie mowa o tym, o ile droższy jest graf odporny na błędy wierzchołkowe w porównaniu z grafem zwykłym.
28.04
Robert Lukotka
Perfect matchings in highly cyclically connected regular graphs
Streszczenie:
A leaf matching operation on a graph consists of removing a vertex of degree~$1$ together with its neighbour from the graph. Let $G$ be a $d$-regular cyclically $(d-1+2k)$-edge-connected graph of even order, where $k ge 0$ and $d ge 3$. We prove that for any given set $X$ of$d-1+k$ edges, there is no $1$-factor of $G$ avoiding $X$ if and only if either an isolated vertex can be obtained by a series of leaf matching operations in $G-X$, or $G-X$ has an independent set that contains more than half of the vertices of~$G$. To demonstrate how to check the conditions of the theorem we prove several statements on $2$-factors of cubic graphs. For $k ge 3$, we prove that given a cyclically $(4k-5)$-edge-connected cubic graph $G$ and three paths of length $k$ such that the distance between any two of them is at least $8k-16$, there is a $2$-factor of $G$that contains one of the paths. We provide a similar statement for two paths when $k=3$ and $k=4$. As a corollary we show that given a vertex $v$ in a cyclically $7$-edge-connected cubic graph, there is a $2$-factor such that $v$ is in a circuit of length greater than $7$.
A leaf matching operation on a graph consists of removing a vertex of degree~$1$ together with its neighbour from the graph. Let $G$ be a $d$-regular cyclically $(d-1+2k)$-edge-connected graph of even order, where $k ge 0$ and $d ge 3$. We prove that for any given set $X$ of$d-1+k$ edges, there is no $1$-factor of $G$ avoiding $X$ if and only if either an isolated vertex can be obtained by a series of leaf matching operations in $G-X$, or $G-X$ has an independent set that contains more than half of the vertices of~$G$. To demonstrate how to check the conditions of the theorem we prove several statements on $2$-factors of cubic graphs. For $k ge 3$, we prove that given a cyclically $(4k-5)$-edge-connected cubic graph $G$ and three paths of length $k$ such that the distance between any two of them is at least $8k-16$, there is a $2$-factor of $G$that contains one of the paths. We provide a similar statement for two paths when $k=3$ and $k=4$. As a corollary we show that given a vertex $v$ in a cyclically $7$-edge-connected cubic graph, there is a $2$-factor such that $v$ is in a circuit of length greater than $7$.
21.04
Konstanty Junosza-Szaniawski
Etykietowanie L(2,1) grafów przedziałowych
Streszczenie:
Etykietowaniem L(2,1) nazywamy funkcję przypisująca wierzchołkom nieujemne liczby całkowite w taki sposób aby etykiety sąsiednich wierzchołków różniły się co najmniej o dwa, a etykiety wierzchołków w odległości 2 miały różne etykiety. Rozpiętością etykietowania L(2,1) nazywamy różnice między największa i najmniejszą etykietą. Rozpiętością L(2,1) grafu G nazywamy najmniejszą możliwą rozpiętością etykietowania L(2,1) grafu G. Dla grafów przecięć przedziałów rozpiętość L(2,1) nie przekracza Delta(G)+omega(G), gdzie Delta(G) oznacza maksymalny stopień, a omega(G) rozmiar najliczniejszej kliki w G.
Etykietowaniem L(2,1) nazywamy funkcję przypisująca wierzchołkom nieujemne liczby całkowite w taki sposób aby etykiety sąsiednich wierzchołków różniły się co najmniej o dwa, a etykiety wierzchołków w odległości 2 miały różne etykiety. Rozpiętością etykietowania L(2,1) nazywamy różnice między największa i najmniejszą etykietą. Rozpiętością L(2,1) grafu G nazywamy najmniejszą możliwą rozpiętością etykietowania L(2,1) grafu G. Dla grafów przecięć przedziałów rozpiętość L(2,1) nie przekracza Delta(G)+omega(G), gdzie Delta(G) oznacza maksymalny stopień, a omega(G) rozmiar najliczniejszej kliki w G.
14.04
Bartłomiej Pawlik
Bezkwadratowe rozszerzenia słów
Streszczenie:
Mówimy, że słowo U zawiera kwadrat, jeżeli U=AXXB dla pewnych słów A, B i pewnego niepustego słowa X. Słowo, które nie zawiera kwadratu nazywamy słowem bezkwadratowym. Rozszerzeniem słowa V=AB nazywamy słowo V=AxB, gdzie x jest literą. Klasyczny wynik Thue'go (1906) mówi, że już nad alfabetem trójelementowym istnieją dowolnie długie słowa bezkwadratowe. W 2019 roku J. Grytczuk, H. Kordulewski i A. Niewiadomski udowodnili, że nad alfabetem trójelementowym istnieje nieskończenie wiele ekstremalnych słów bezkwadratowych (tj. słów bezkwadratowych, których każde rozszerzenie jest kwadratem). W niniejszym referacie przedstawię kilka wyników i hipotez związanych z dalszymi badaniami zagadnień związanych z rozszerzaniem słów bezkwadratowych.
Mówimy, że słowo U zawiera kwadrat, jeżeli U=AXXB dla pewnych słów A, B i pewnego niepustego słowa X. Słowo, które nie zawiera kwadratu nazywamy słowem bezkwadratowym. Rozszerzeniem słowa V=AB nazywamy słowo V=AxB, gdzie x jest literą. Klasyczny wynik Thue'go (1906) mówi, że już nad alfabetem trójelementowym istnieją dowolnie długie słowa bezkwadratowe. W 2019 roku J. Grytczuk, H. Kordulewski i A. Niewiadomski udowodnili, że nad alfabetem trójelementowym istnieje nieskończenie wiele ekstremalnych słów bezkwadratowych (tj. słów bezkwadratowych, których każde rozszerzenie jest kwadratem). W niniejszym referacie przedstawię kilka wyników i hipotez związanych z dalszymi badaniami zagadnień związanych z rozszerzaniem słów bezkwadratowych.
Na podstawie pracy wspólnej z Jarosławem Grytczukiem i Hubertem Kordulewskim.
07.04
Andrzej Ruciński
Twins in (random) permutations
Streszczenie:
We define several variants of the notion of twins (and multiple twins) in permutations and study their presence in both, permutations and random permutations. The main question of how large twins can be found in these structures has gotten so far rather imprecise answers with lower and upper bounds rarely matching each other. Consequently, during the lecture several open problems will be stated.
We define several variants of the notion of twins (and multiple twins) in permutations and study their presence in both, permutations and random permutations. The main question of how large twins can be found in these structures has gotten so far rather imprecise answers with lower and upper bounds rarely matching each other. Consequently, during the lecture several open problems will be stated.
This is joint work with A. Dudek and J. Grytczuk.
31.03
Sebastian Czerwiński
Hipoteza Grytczuka dla kostek kombinatorycznych
Streszczenie:
Kostką kombinatoryczną nazywamy zbiór $A=A_1times dots times A_d$, gdzie zbiory $A_i$ są skończone i co najmniej dwuelementowe. Podziałem kostki $A$ nazywamy rodzinę $mathcal{B}={B^1,dots ,B^m}$ podkostek właściwych kostki $A$, tzn. elementy zbioru $mathcal{B}$ są postaci $B=B_1timesdots times B_d$, gdzie $B_i$ jest podzbiorem właściwym $A_i$, dla $iin[d]$. Alon, Bohman, Holzman and Kleitman udowodnili, że $mgeq 2^d$.
Kostką kombinatoryczną nazywamy zbiór $A=A_1times dots times A_d$, gdzie zbiory $A_i$ są skończone i co najmniej dwuelementowe. Podziałem kostki $A$ nazywamy rodzinę $mathcal{B}={B^1,dots ,B^m}$ podkostek właściwych kostki $A$, tzn. elementy zbioru $mathcal{B}$ są postaci $B=B_1timesdots times B_d$, gdzie $B_i$ jest podzbiorem właściwym $A_i$, dla $iin[d]$. Alon, Bohman, Holzman and Kleitman udowodnili, że $mgeq 2^d$.
Na seminarium przedstawię dowód tego twierdzenia, oraz omówię kilka uogólnień tego wyniku, oraz hipotezę Grytczuka z moimi częściowymi wynikami.
24.03
Jakub Kwaśny
Kolorowania krawędziowe grafów rozróżniające wierzchołki sąsiednie
17.03
Piotr Micek
Wymiar, wysokość i standardowe przykłady w porządkach planarnych
Streszczenie:
Będzie to wprowadzenie do współczesnych badań nad wymiarem częściowych porządków. Już Dilworth wykazał, że częściowe porządki (posety) o dużym wymiarze muszą być szerokie. Nie muszą one jednak być wysokie. Rzeczywiście, tzw. standardowe przykłady to posety o wysokości 2 i nieograniczonym wymiarze. Okazuje się, że posety planarne o dużym wymiarze muszą być zarówno szerokie, jak i wysokie. Innymi słowy, wymiar porządków planarnych jest ograniczony w terminach wysokości. Rozpoczynając od podstaw przeprowadzimy parę pełnych rozumowań dowodzących ograniczenia na wymiar. Zobaczymy, że założenie o planarności w powyższej wypowiedzi można istotnie osłabić. Określimy obecny front badań i wyznaczymy najważniejsze wyzwania w strukturalnej teorii posetów. Wspomnimy o dim-ograniczoności oraz o wymiarze Boolowskim.
10.03
Zofia Miechowicz
Nowe spojrzenie na złamane cykle w grafach
Streszczenie:
Jednym z ciekawszych twierdzeń w teorii grafów jest słynne twierdzenie Whitneya o złamanych cyklach. Już w 1932 roku Whitney wykazał związek pomiędzy wielomianem chromatycznym grafu a liczbą ukrytych w nim pewnych ciekawych struktur. W referacie tym postaram się zainteresować słuchaczy zarówno samą zależnością jak i strukturami, które opisuje. Przedstawię przegląd wybranych wyników dotyczących złamanych cykli w oryginalnym ujęciu oraz zaproponuję pewne naturalne ich uogólnienie, które pojawiło się w toku badań nad problemem pozornie niezwiązanym z wynikami Whitneya. Dla tak uogólnionych złamanych cykli zaproponuję kolorowanie i postaram się możliwie szeroko kolorowanie to scharakteryzować.
03.03
Seminarium odwołane
24.02
Zbigniew Lonc
Jak sprawiedliwie podzielić graf?
Streszczenie:
Przypuśćmy, że mamy m dóbr niepodzielnych i n agentów, którzy mają sprawiedliwie rozdzielić te dobra między siebie. Każde dobro ma pewną wartość dla każdego agenta, przy czym dane dobro może mieć różną wartość dla różnych agentów. 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. Zakładamy, że każdy agent x dzieli zbiór dóbr tak, żeby mieć pewność, że dostanie dobra o jak największej sumarycznej wartości niezależnie od wyborów innych agentów. Oznaczmy tę największą wartość przez m(x). Agent x uważa rzeczywisty podział za sprawiedliwy, jeśli dostanie dobra o wartości co najmniej m(x). Ten rzeczywisty podział nazywamy MMS-podziałem, jeśli każdy z n agentów uważa go za sprawiedliwy. Załóżmy teraz, że zbiór dóbr ma pewną strukturę. Dokładniej, dobra są wierzchołkami pewnego spójnego grafu G. Nie wszystkie podziały zbioru dóbr między n agentów są teraz dozwolone, lecz jedynie takie gdzie każdy agent dostaje zbiór dóbr indukujący spójny podgraf grafu G.
Nie dla wszystkich grafów dóbr MMS-podział istnieje dla dowolnych agentów. Wiadomo, że istnieje dla drzew. W przypadku grafów pełnych udowodniono, że można zawsze podzielić graf dóbr w ten sposób, żeby każdy agent x otrzymał dobra o wartości co najmniej 3m(x)/4, a w przypadku cykli, o wartości co najmniej 0.618m(x). Otwartym jest pytanie czy istnieje taka stała c>0, że dla dowolnego grafu dóbr i dowolnych agentów, istnieje podział tego grafu, w którym każdy agent x otrzymuje dobra o wartości co najmniej cm(x). Podczas referatu pokazany zostanie między innymi szkic dowodu, że jeśli graf dóbr jest K_{1,3}-wolny, to dla dowolnych agentów istnieje podział tego grafu, w którym każdy agent x otrzymuje dobra o wartości co najmniej m(x)/2. Zaprezentowanych również zostanie kilka innych otwartych problemów dotyczących sprawiedliwych podziałów grafów dóbr.
03.02, 10.02, 17.02
Sesja - seminarium odwołane
27.01
Jakub Przybyło
Jak nieregularny może być graf regularny
Streszczenie:
Siła nieregularności grafu prostego G, s(G), definiowana jest jako najmniejsze k, dla którego istnieje przypisanie wag ze zbioru {1,2,...,k} krawędziom grafu G indukujące parami różne ważone stopnie wszystkich wierzchołków, lub równoważnie – najmniejsza możliwa maksymalna wielokrotność krawędzi w nieregularnym multigrafie otrzymanym z G przez zwielokrotnienie jego wybranych krawędzi. Centralnym problemem otwartym dotyczącym tego parametru jest hipoteza sformułowana w pracy z 1987 roku, której autorami byli Faudree i Lehel. Sugeruje ona, iż istnieje stała C taka, że s(G) nie przekracza wartości n/d+C dla każdego d-regularnego grafu G o n wierzchołkach i d>1 (podczas gdy elementarne rozumowanie polegające na podwójnym zliczaniu implikuje, iż s(G)>n/d). Najlepszy znany wynik dotyczący postulowanego ograniczenia górnego gwarantuje, że s(G)< 6+6n/d. Podczas referatu zarysuję ideę dowodu, iż hipoteza ta jest asymptotycznie prawdziwa, jeżeli tylko d nie jest ani zbyt małe, ani zbyt duże w stosunku do n.
20.01
Marcin Anholcer
Problem Dinitza, hipoteza o kolorowaniu z list i przydziały stabilne
Streszczenie:
Załóżmy, że dana jest macierz kwadratowa o $n$ wierszach i kolumnach, której każdemu elementowi przypisano listę $n$ kolorów. Czy można tak wybrać po jednym kolorze z każdej listy, aby każdy wiersz i każda kolumna były tęczowe? Problem ten (tzw. problem Dinitza) jest szczególnym przypadkiem hipotezy o kolorowaniu z list (List Coloring Conjecture, LCC), gdzie każdej krawędzi grafu przypisujemy listę złożoną z tylu kolorów, ile wynosi indeks chromatyczny tego grafu. Hipoteza mówi, że dla każdego grafu można wybrać z list po jednym kolorze i uzyskać w ten sposób poprawne kolorowanie krawędziowe. LCC dla grafów dwudzielnych, czyli problem Dinitza (a w zasadzie jego ogólniejszą wersję dla multigrafów dwudzielnych) rozwiązał Galvin, wykorzystując jądra digrafów. W pracy wspomniał o możliwym wyrażeniu części dowodu w języku stabilnych przydziałów, choć nie skorzystał z tej możliwości. Wykorzystał ją natomiast Fleiner, który uogólnił wynik na grafy, w których listy przypisane do dowolnego nieparzystego cyklu nie mają wspólnego koloru. W czasie wystąpienia przedstawię dowody obu twierdzeń.
13.01
Przemysław Gordinowicz
Błądząc po grafie, albo czego nie wiem o łańcuchach Markowa
Streszczenie:
Motywacją dla tego referatu jest problem postawiony w pracy [1], dotyczący przekazywania sygnału (albo wirusa) przez agentów poruszających się po pewnym grafie: jak oszacować czas propagacji sygnału dla grafów pewnych klas w zależności od liczby agentów .
Wydaje się, że istotnym narzędziem dla rozwiązania tego problemu jest analiza wielu współbieżnych błądzeń losowych, zapoczątkowana pracą [3]. Jest to dziedzina, o której wciąż, jako ludzkość, wiemy niewiele - choć od niedawna trochę więcej [4]. Celem wystąpienia jest zapoznanie uczestników seminarium (a w szczególności referującego) z tą tematyką. Z uwagi na dużą rozbieżność między poziomem zaawansowania prac [3, 4] a wiedzą referującego w dziedzinie łańcuchów Markowa, ich prezentacja zostanie poprzedzona wprowadzeniem w teorię błądzeń po grafach w oparciu o świetną książkę [2].
1. R. Huq, B. Kamiński, A. Mashatan, P. Prałat, P. Szufel, On Broadcasting Time in the Model of Travelling Agents..
2. D.A. Levin, Y. Peres, E.L. Wilmer, Markov Chains and Mixing Times, second edition, (AMS, 2008 - first edition)
3. N. Alon, C. Avin, M. Koucky, G. Kozma, Z. Lotker, M.R. Tuttle, Many random walks are faster than one, Combin. Probab. Comput., 20 (2011), 481-502
4. N. Rivera, T. Sauerwald, J. Sylvester, Multiple Random Walks on Graphs: Mixing Few to Cover Many
23.12
Marcin Anholcer
Stabilność w wielostronnych zagadnieniach przydziału
Streszczenie:
Gale i Shapley (1962) pokazali, że w przypadku dwóch równolicznych zbiorów osób, które mają określone preferencje odnośnie do osób z drugiego zbioru, zawsze można znaleźć stabilny przydział (skojarzenie), a nawet, że można to zrobić w wielomianowym czasie. Knuth (1976) zadał pytanie, czy tę cechę mają również zadania, w których występują co najmniej trzy grupy osób. Dość szybko okazało się, że nie zawsze. Od tamtej pory wiele osób zastanawiało się, jaki układ preferencji gwarantuje istnienie stabilnego przydziału. W trakcie wystąpienia opowiem o tych rozważaniach.
16.12
Paweł Naroski
Nie czas żałować róż, gdy płoną grafy
Streszczenie:
Wyobraźmy sobie graf wykonany z łatwopalnego materiału. Jeśli podpalimy wierzchołek takiego grafu, to będzie on płonął. Umówmy się, że nieskończenie długo. Dodatkowo pożar będzie propagował się wzdłuż krawędzi - jeśli w rundzie $i$ dany wierzchołek płonie, to w rundzie $i+1$ będą płonąć wszyscy jego sąsiedzi. Zakładając, że w każdej rundzie mamy prawo podpalić jeden wierzchołek pytamy ile rund wystarcza, aby pożar objął wszystkie wierzchołki zadanego grafu.
Opisanym wyżej problemem zajmowało się wielu znakomitych uczonych, m. in. Noga Alon, który udowodnił nieco zaskakujący fakt, że $n$-wymiarowej kostki $Q_n$ nie można spalić w sufit z przepołowionego $n$ rund. Fakt ten jest zaskakujący dlatego, że w liczbę rund o $1$ większą od powyższej można ten graf spalić korzystając z prawa do podpalenia wierzchołka jedynie w pierwszych dwóch rundach.
Zreferuję pracę zawierającą opisany wyżej wynik. Praca ta jest stara, ale z wielu względów ciekawa. Jakich względów? A to już zapraszam na referat.
N. Alon, Transmitting in the $n$-dimensional cube, Discrete Applied Mathematics 37/38, 1992, str. 9-11.
09.12
Mariusz Zając
Wielomany grafowe i mnogość poprawnych kolorowań
Streszczenie:
Wiele twierdzeń chromatycznej teorii grafów gwarantuje istnienie co najmniej jednego (lub nieistnienie żadnego) kolorowania wierzchołków grafów pewnej klasy.
Dzięki zastosowaniu metod wielomianowych często można dość szybko wykazać, że liczba owych pokolorowań wynosi co najmniej c^|V|, przy czym stała c może być istotnie większa niż uzyskana przez wcześniejszych badaczy trudniejszymi metodami.
(jest to wstępne sprawozdanie z rozmyślań zespołu: B. Bosek, J. Grytczuk, G. Gutowski, O. Serra, M.
(jest to wstępne sprawozdanie z rozmyślań zespołu: B. Bosek, J. Grytczuk, G. Gutowski, O. Serra, M.
02.12
Karolina Okrasa
Vertex deletion into bipartite permutation graphs
Streszczenie:
A class C of graphs is hereditary, if it is closed under vertex deletion. For some fixed class C, the Vertex deletion into C problem takes an instance (G,k), where G is an arbitrary graph and k is an integer, and asks whether it is possible to delete at most k vertices from G to obtain a graph which belongs to C. In particular, vertex deletion problem into any non-trivial hereditary class of graphs is NP-hard [Lewis and Yannakakis, JCSS 1980].
A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines p1 and p2, one on each. A bipartite permutation graph is a permutation graph which is bipartite. Since bipartite permutation graphs form a hereditary graphs class, they can be uniquely characterized in terms of minimal forbidden induced subgraphs: a graph is a bipartite permutation graph if and only if it does not contain any graph from some family F as an induced subgraph. During the talk I am going to define a class of almost bipartite permutation graphs and show how we can exploit their structure to show that the Vertex deletion into bipartite permutation graphs problem is fixed-parameter tractable (with respect to k).
This is a joint work with Łukasz Bożyk, Jan Derbisz, Tomasz Krawczyk, and Jana Novotná.
25.11
Edward Szczypka
Przykłady wykorzystania metody kompresji w matematyce dyskretnej i algorytmach
18.11
Marta Piecyk
Complexity of the list homomorphism problem for graphs with bounded cutwidth
Streszczenie:
A homomorphism from a graph G to a graph H is an edge preserving mapping f: V(G) -> V(H). If G is given with lists L: V(G) -> 2^V(H), we say that f is a list homomorphism if it additionaly respects lists L. As for H=K_k, a homomorphism f: V(G) -> V(H) can be seen as k-coloring of G, (list) homomorphisms are natural extension of (list) colorings.
Recently, Jansen and Nederlof [ESA 2018] showed an algorithm solving (List)-k-Coloring in time c^ctw(G) * n^O(1), where c is a constant that does not depend on k. This is very unusual, as for many graph parameters t(G) (for example treewidth, pathwidth, the size of a minimum feedback vertex set) algorithms solving k-Coloring in time k^t(G) * n^O(1) are optimal under common complexity assumptions.
A natural question is if we can extend these results to graph homomorphisms. Altough we showed that there is no constant c such that for every H, homomorphism problem can be solved in time c^ctw(G) * n^O(1), I will show how to extend the algorithm of Jansen and Nederlof, so that it works for list homomorphisms in slightly worse time.
Joint work with Paweł Rzążewski.
Recently, Jansen and Nederlof [ESA 2018] showed an algorithm solving (List)-k-Coloring in time c^ctw(G) * n^O(1), where c is a constant that does not depend on k. This is very unusual, as for many graph parameters t(G) (for example treewidth, pathwidth, the size of a minimum feedback vertex set) algorithms solving k-Coloring in time k^t(G) * n^O(1) are optimal under common complexity assumptions.
A natural question is if we can extend these results to graph homomorphisms. Altough we showed that there is no constant c such that for every H, homomorphism problem can be solved in time c^ctw(G) * n^O(1), I will show how to extend the algorithm of Jansen and Nederlof, so that it works for list homomorphisms in slightly worse time.
Joint work with Paweł Rzążewski.
11.11
Seminarium odwołane
04.11
Paweł Rzążewski
Quasi-polynomial-time algorithms for Independent Set and related problems in P_t-free graphs
Streszczenie:
The complexity of the Independent Set problem in P_t-free graphs, i.e., graphs that do not contain a path on t vertices as an induced subgraph,is one of the main open problems concerning algorithms for restricted graph classes. The problem is known to be polynomial-time-solvable for t <= 6. Unfortunately the proof is fine-tailored for this class of graphs and our current algorithmic toolbox seems insufficient to provide a polynomial-time algorithm for P_t-free graphs, for every fixed t.
In the recent breakthrough, Gartland and Lokshtanov [FOCS 2020] gave a quasi-polynomial-time algorithm for the problem in P_t-free graphs: their algorithm runs in time n^O(log^3n), where t is assumed to be a constant. Inspired by their ideas, Pilipczuk, Pilipczuk, and Rzążewski [accepted to SOSA 2021] showed an arguably simpler algorithm with an improved running time bound of n^O(log^2 n).
During the talk I will present the simplified algorithm and discuss very recent extensions of this approach to different problems, including 3-Coloring and Feedback Vertex Set.
Joint work with Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk.
In the recent breakthrough, Gartland and Lokshtanov [FOCS 2020] gave a quasi-polynomial-time algorithm for the problem in P_t-free graphs: their algorithm runs in time n^O(log^3n), where t is assumed to be a constant. Inspired by their ideas, Pilipczuk, Pilipczuk, and Rzążewski [accepted to SOSA 2021] showed an arguably simpler algorithm with an improved running time bound of n^O(log^2 n).
During the talk I will present the simplified algorithm and discuss very recent extensions of this approach to different problems, including 3-Coloring and Feedback Vertex Set.
Joint work with Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk.
28.10
Jarosław Grytczuk
Od hipotezy 1-2-3 do hipotezy Roty
Streszczenie:
Przedstawię kilka powiązanych problemów otwartych, których wspólną cechą jest poszukiwanie kolorowania danej struktury kombinatorycznej unikającego zerowania się form liniowych przypisanych określonym podstrukturom. Korowód otworzy znana hipoteza 1-2-3, a zamknie słynna hipoteza Roty o bazach. Po drodze pojawią się mniej znane przypuszczenia, np. hipoteza Saxtona o permanencie (pociągająca listową wersję hipotezy 1-2-3), czy hipoteza Goddyna-Tarsi'ego o nieznikających transwersalach.