Aktualny program seminarium
Jeśli chcesz otrzymywać regularnie aktualny plan referatów, to napisz do sekretarza seminarium.
| 7.05.2025 | Konstanty Junosza-Szaniawski | PW |
| Dowód hipotezy Exoo o kolorowaniu płaszczyzny | ||
| \(\quad\)W referacie przedstawię wyniki pracy Vsevoloda Voronova [1] dotyczącej wariantu klasycznego problemu Hadwigera–Nelsona, związanego z chromatyczną liczbą płaszczyzny. W rozważanym wariancie celem jest wyznaczenie minimalnej liczby kolorów potrzebnych do pokolorowania płaszczyzny euklidesowej tak, aby dowolne dwa punkty, których odległość zawiera się w przedziale [1−ε, 1+ε] (dla dowolnie małego ε>0), miały różnie kolory. G. Exoo [2] w 2004 roku postawił hipotezę, że niezależnie od wartości ε, konieczne jest użycie co najmniej 7 kolorów. Głównym rezultatem omawianej pracy jest dowód prawdziwości tej hipotezy dla płaszczyzny euklidesowej. [1] https://arxiv.org/abs/2304.10163 [2] Exoo, G.: ε-Unit distance graphs. Discrete Comput. Geom. 33, 117–123 (2005) | ||
| 14.05.2025 | Seminarium odwołane | |
| Obowiązuje plan piątkowy na PW. | ||
| 21.05.2025 | Igor Grzelec | AGH |
| Lokalna nieregularność grafów, multigrafów i digrafów | ||
| \(\quad\) Mówimy, że graf jest lokalnie nieregularny, jeśli każde dwa sąsiednie wierzchołki mają różne stopnie. Referat będzie dotyczył zarówno hipotez dla których znane są już częściowe rezultaty, jak na przykład hipotezy o rozkładzie grafu na trzy podgrafy lokalnie nieregularne, która jest analogiem hipotezy 1-2-3, czy też hipotezy (2,2) mówiącej, że graf spójny o co najmniej czterech wierzchołkach można rozłożyć na dwa grafy, w których możemy rozróżnić sąsiednie wierzchołki sumami za pomocą co najwyżej dwóch kolorów, jak i nowych postawionych niedawno w pracach mojego współautorstwa. Po wstępie dotyczącym hipotezy 1-2-3 wraz z jej analogiem wspomnianym powyżej przedstawimy trzy wersje hipotezy (2,2) oraz rezultaty, potwierdzające te warianty dla wybranych klas grafów. W kolejnej części referatu sformujemy nowy problem dotyczący lokalnej nieregularności grafów związany z hipotezą (2,2) i hipotezą o rozkładzie grafu na trzy podgrafy lokalnie nieregularne, jak również zaprezentujemy jego częściowe rozwiązanie. W następnej części postawimy hipotezę o rozkładnie multigrafu powstałego z grafu \(G\) przez podwojenie wszystkich krawędzi \(G\) na dwa multigrafy lokalnie nieregularne i potwierdzimy ją dla wybranych klas grafów. Ponadto podamy ograniczenia górne na liczbę lokalnie nieregularnych multigrafów występujących w rozkładzie dowolnego takiego multigrafu i wybranych klas multigrafów. Na koniec rozważamy dwa nowe sposoby definiowania lokalnie nieregularnego digrafu, sformujemy dwie hipotezy dotyczące rozkładów digrafów na digrafy lokalnie nieregularne i zaprezentujemy szereg rezultatów dla poparcia tych hipotez. \(\quad\)Przedstawione zagadnienia zostały zawarte w mojej rozprawie doktorskiej, której promotorem jest Mariusz Woźniak i powstały we współpracy z grupą badawczą z Ústav matematiky, Univerzita Pavla Jozefa Šafárika v Košiciach oraz grupą badawczą z Laboratoire Bordelais de Recherche en Informatique w Bordeaux. | ||
| 28.05.2025 | Magdalena Prorok | AGH |
| Szczegóły wkrótce. | ||
Archiwalny program seminarium (rok akademicki 2024/2025)
| 23.04.2025 | Paweł Rzążewski | PW |
| Przecięcia najdłuższych ścieżek w grafie | ||
| \(\quad\)Wiadomo z ćwiczeń, że w grafie spójnym każde dwie najdłuższe ścieżki mają wspólny wierzchołek. Gallai zadał naturalne pytanie: czy najdłuższe ścieżki w grafie spójnym mają własność Helly'ego, czyli czy istnieje wierzchołek należący do wszystkich najdłuższych ścieżek? Podczas referatu opowiem o kilku rzeczach, które wiadomo o tym problemie. | ||
| 9.04.2025 | Mariusz Zając | PW |
| Wielomiany i kolorowanie hipergrafów | ||
| \(\quad\)Używanie metod algebry wielomianów do badania własności kolorowań grafów nie jest nową koncepcją. Jednym z ważniejszych używanych tu narzędzi jest wykazane w 1999 roku przez N. Alona twierdzenie, znane Combinatorial Nullstellensatz. W swoim referacie przedstawię próbę uogólnienia pewnych znanych wcześniej wyników na hipergrafy. Już na początku okaże się przy tym, że nawet podstawowe definicje (np. wielomianu grafowego) można uogólniać na różne i nierównoważne sposoby. Będzie to wybór z pracy https://arxiv.org/abs/2501.00157, której pozostałymi autorami są M. Anholcer, B. Bosek, G. Gutowski, M. Lasoń, J. Przybyło, O. Serra, M. Tuczyński i L. Vena. | ||
| 2.04.2025 | Sylwia Cichacz-Przeniosło | AGH |
| Zastosowanie zero-podzbiorów w etykietowaniach grafów | ||
| \(\quad\)Niech \((\Gamma,+)\), będzie będzie skończoną grupą przemienną. Podzbiór \(S\) zbioru elementów \(\Gamma\) nazywamy zero-podzbiorem, jeśli \(\sum_{a\in S} a=0\). \(\quad\)Jednym z kluczowych zagadnień w tym temacie, jest szukanie rozłącznych zero-podzbiorów w \(\Gamma\). Podejście to zostało zainspirowane badaniami nad trójkami Steinera i zapoczątkowane przez Skolema. \(\quad\)Co ciekawe, pewne etykietowania grafów typu magicznego są ściśle związane z rozłącznymi zero-podzbiorami. W trakcie referatu zbadamy niektóre z tych powiązań. | ||
| 26.03.2025 | Hubert Grochowski | PW |
| Najkrótsza ścieżka z rozdzieleniem budżetu - gra kombinatoryczna | ||
| \(\quad\)Znalezienie optymalnych strategii dla graczy w przypadku wielu gier kombinatorycznych stanowi niełatwe zadanie. W wielu przypadkach, interesuje nas wyznaczenie strategii dla graczy dla konkretnej instancji gry - na przykład dla konkretnego grafu. W trakcie referatu przedstawię efektywny sposób generowania w takim przypadku strategii dla graczy z wykorzystaniem programowania liniowego dla gry min-maxowej "Najkrótsza ścieżka z rozdzieleniem budżetu". \(\quad\)W grze, która odbywa się na ważonym grafie G, jeden z graczy wybiera ścieżkę pomiędzy dwoma ustalonymi wierzchołkami s oraz t w grafie G, zaś drugi gracz, dysponujący ustalonym budżetem, w tym samym momencie rozdziela go na krawędzie grafu, zwiększając przy tym wagi niektórych krawędzi. \(\quad\)Współautorzy: Armin Fügenschuh (BTU Cottbus-Senftenberg), Konstanty Junosza-Szaniawski | ||
| 19.03.2025 | Jarosław Grytczuk | PW |
| Słowa i grafy uporządkowane | ||
| \(\quad\)Przedstawię kilka problemów dotyczących słów i grafów uporządkowanych. Na przykład, rozważmy taką oto niewinną zagadkę: Czy słowo postaci ABBAABBAABBA...ABBA, składające się z nieparzystej liczby bloków ABBA, da się rozłożyć na dwa identyczne podsłowa? \(\quad\)Rozłożyć, znaczy tyle co móc pokolorować litery słowa dwoma kolorami tak, aby podsłowa czytane osobno w każdym kolorze, z zachowaniem porządku od lewej do prawej, były identyczne. Problem postawił Andrzej Komisarski, w kontekście szerszej hipotezy o słowach mających taką własność rozkładu (znanych jako przetasowane kwadraty), a jako pierwszy rozwiązanie "informatyczne" znalazł Wojciech Fortuna. Odpowiedź brzmi: NIE. Warto zaznaczyć, że ogólny problem decyzyjny, polegający na stwierdzeniu czy dane słowo jest przetasowanym kwadratem, jest NP-zupełny (nawet w ograniczeniu do słów binarnych). \(\quad\)Przedstawię inne podejście bazujące na grafach uporządkowanych, które wydaje się być bardziej uniwersalne. Oprócz tego być może przedstawię kilka innych problemów leżących w pobliżu, o ile uda mi się rozstrzygnąć dylemat, czy lepiej mniej, a dokładniej, czy więcej i mniej dokładnie. Jak mawiał Eugeniusz Kowalski, "ten dylemat zawsze jest". \(\quad\)Współautorzy: Bartłomiej Pawlik i Andrzej Ruciński | ||
| 26.02.2025 | Sebastian Babiński | Uniwersytet Jagielloński |
| Kolorowe problemy Turána | ||
| \(\quad\)Jednym z najważniejszych problemów ekstremalnej teorii grafów jest wyznaczenie liczby Turána grafu F, czyli największej możliwej liczby krawędzi w grafie, który nie zawiera F jako podgrafu. Dla F będącego trójkątem rozwiązaniem problemu jest klasyczne twierdzenie Mantela, natomiast Erdős i Gallai wyznaczyli asymptotycznie optymalne ograniczenie liczby Turána dla ścieżki o ustalonej długości. \(\quad\)Uogólnieniem powyższych zagadnień są tzw. kolorowe problemy Turána. Dla ustalonego zabronionego grafu F rozważamy c grafów o wspólnym zbiorze wierzchołków, każdy z grafów interpretujemy jako krawędzie w innym kolorze. Celem jest wyznaczenie największej możliwej liczby krawędzi w każdym kolorze, przy której nie pojawia się tęczowa kopia grafu F, czyli taka która ma wszystkie krawędzie w różnych kolorach. Problem ten został rozwiązany w przypadku, gdy F jest trójkątem (wyniki różnią się w zależności od tego, czy liczba kolorów jest równa, czy większa niż 3). \(\quad\)W trakcie referatu zaprezentowane zostaną wyniki związane z kolorowymi problemami Turána. Pierwsza część dotyczy sytuacji, gdy F jest ścieżką o 3 krawędziach w przypadku dowolnej ustalonej liczby kolorów. W drugiej części przedstawione zostaną wyniki dla grafów skierowanych nieposiadających tęczowych trójkątów skierowanych lub tranzytywnych oraz dla dowolnej ustalonej liczby kolorów. Ograniczenia na liczby krawędzi, które zostaną omówione, są asymptotycznie optymalne. \(\quad\)Współautorzy: Andrzej Grzesik, Magdalena Prorok. | ||
| 22.01.2025 | Tomasz Krawczyk | PW |
| O pewnym uogólnieniu problemu zbioru dominującego | ||
| \(\quad\)Na swoim referacie wprowadzę pewne uogólnienie problemu zbioru dominującego w grafie, wyrażonego w terminach rozkładu żetonów po wierzchołkach grafu. \(\quad\)Rozkładając żetony po wierzchołkach zbioru dominującego grafu spełniony jest warunek, że dla każdego wierzchołka grafu albo na tym wierzchołku albo na pewnym jego sąsiedzie leży żeton. Własność tę chcemy teraz wzmocnić tak, aby teraz dla każdego zbioru A liczności co najwyżej k każdy wierzchołek tego zbioru mógł wybrać swój prywatny żeton, który znajduje się na tym wierzchołku lub pewnym jego sąsiedzie. \(\quad\)Rozkład żetonów po wierzchołkach grafu (na jednym wierzchołku można umieścić kilka żetonów), który posiada taką własność, nazywamy k-zabezpieczającym. Oczywiście, rozkład żetonów jest 1-zabezpieczający jeżeli wierzchołki z żetonem odpowiadają zbiorowi dominującemu w grafie. \(\quad\)W trakcie referatu zaprezentuję kilka prostych wyników złożonościowych dotyczących problemów związanych z k-zabezpieczającymi rozkładami żetonów w grafie. \(\quad\)Pokażę, że: - problem testowania, czy rozkład żetonów jest k-zabezpieczający, jest NP-zupełny, zaś parametryzowany liczbą k jest W[1]-trudny, - problem testowania, czy rozkład żetonów w grafie planarnym jest k-zabezpieczający, należy do klasy FPT, - problem testowania, czy istnieje k-zabezpieczający rozkład wykorzystujący co najwyżej n żetonów, jest Sigma^P_2-zupełny. | ||
| 15.01.2025 | Paweł Prałat | Toronto Metropolitan University |
| Asynchronous Majority Dynamics on Binomial Random Graphs | ||
| \(\quad\)We study information aggregation in networks when agents interact to learn a binary state of the world. Initially each agent privately observes an independent signal which is correct with probability \(1/2+\delta\) for some \(\delta > 0\). At each round, a node is selected uniformly at random to update their public opinion to match the majority of their neighbours (breaking ties in favour of their initial private signal). Our main result shows that for sparse and connected binomial random graphs \(G(n,p)\) the process stabilizes in a correct consensus in \(O(n\log^2 n/\log\log n)\) steps with high probability. In fact, when \(\log n/n \ll p = o(1)\) the process terminates at time \(\hat T = (1+o(1))n \log n\), where \(\hat T\) is the first time when all nodes have been selected at least once. However, in dense binomial random graphs with \(p=\Omega(1)\), there is an information cascade where the process terminates in the incorrect consensus with probability bounded away from zero. | ||
| 8.01.2025 | Seminarium odwołane | |
| Obowiązuje plan poniedziałkowy na PW. | ||
| 18.12.2024 | Zbigniew Lonc | PW |
| O sprawiedliwych podziałach drzew | ||
| \(\quad\)Załóżmy, że mamy zbiór niepodzielnych dóbr, które są reprezentowane jako wierzchołki grafu, oraz zbiór agentów. Każdy agent dysponuje funkcją użyteczności, która przypisuje każdemu dobru określoną wartość, odzwierciedlając jego subiektywną ocenę. Naszym celem jest podział tego zbioru między agentów w sposób spełniający określone kryterium sprawiedliwości, przy czym każda część przypisana agentowi musi stanowić spójny podgraf w grafie dóbr. Koncentrujemy się na tzw. kryterium maksyminimalnym. Wiadomo, że jeśli graf dóbr jest drzewem, to podział zapewniający każdemu agentowi jego spójną część o akceptowanej przez niego wartości zawsze istnieje. Rozważmy teraz analogiczny problem, w którym zamiast dóbr występują "antydobra", tj. wierzchołki drzewa mają ujemne wartości dla wszystkich agentów. Taka sytuacja występuje na przykład wtedy, gdy dzielmy się uciążliwymi obowiązkami. Problem, czy w takim modelu możliwe jest podzielenie drzewa między agentów w sposób spełniający maksyminimalne kryterium sprawiedliwości, jest otwarty. W referacie pokażemy wyniki częściowo potwierdzające hipotezę, że tak w istocie jest. | ||
| 11.12.2024 | Tibor Szabó | Freie Universität Berlin |
| Global rigidty of random graphs in \(\mathbb{R}\) | ||
| \(\quad\)We are interested in the distances between all pairs of points in a set \(P \subseteq \mathbb{R}\), but we only have access to the distances between some of them. Which properties of the graph \(G\) of known distances on the vertex set \(P\) are sufficient for the unique ''reconstruction'' of \(P\), up to isometry? It is computationally difficult to decide about an input graph whether it reconstructs every point set and we investigate how the random graph does. Resolving a conjecture of Benjamini and Tzalik, we prove that as soon as the random graph process has minimum degree 2 with high probability it can reconstruct the distances in any point set in \(\mathbb{R}\). We also study the possibility/limitation of reconstruction of the distances among almost all points using much sparser random graphs. In this direction we resolve a question of Girao, Illingworth, Michel, Powierski, and Scott. Joint work with Richard Montgomery, Rajko Nenadov, and Julien Portier. | ||
| 4.12.2024 | Michał Ziembowski | PW |
| Algebry ścieżek Leavitta | ||
| Niech K będzie ciałem, a E skierowanym grafem. Podczas referatu przedstawiona zostanie konstrukcja bogatej klasy maksymalnych przemiennych podalgebr algebry ścieżek Leavitta L_K(E), co stanowi daleko idące uogólnienie konstrukcji tzw. jądra przemiennego algebry L_K(E). | ||
| 27.11.2024 | Václav Blažej | University of Warwick |
| On the Parameterized Complexity of Eulerian Strong Component Arc Deletion | ||
| \(\quad\)In this talk we will explore the Eulerian Strong Component Arc Deletion problem, where the input is a directed multigraph and the goal is to delete the minimum number of arcs to ensure every strongly connected component of the resulting digraph is Eulerian. This problem is a natural extension of the Directed Feedback Arc Set problem. The complexity of the problem, when parameterized by solution size (i.e., size of the deletion set), has remained unresolved and has been highlighted in several papers. We answer this question and conduct a broad analysis of the problem with respect to other natural parameterizations. | ||
| 20.11.2024 | Nadzieja Hodur | AGH |
| 3-kolorowalność i podgrafy zabronione | ||
| \(\quad\)Mówimy, że graf G jest grafem bez H, jeśli G nie zawiera H jako podgrafu indukowanego. Bykiem nazywamy graf K_3 z dwiema dodatkowymi krawędziami wiszącymi, incydentnymi do dwóch różnych wierzchołków trójkąta. W klasie grafów bez byka problem 3-kolorowalności pozostaje NP-zupełny. Jednak w klasie grafów bez byka i bez jednej z gwiazd, S(1, 1, 2) lub S(1, 2, 2), można znaleźć wielomianowy algorytm rozstrzygający 3-kolorowalność, zwracający 3-kolorowanie właściwe danego grafu, jeżeli takie istnieje, lub prosty podgraf, wymagający większej liczby kolorów, jeżeli dany graf nie jest 3-kolorowalny. \(\quad\)W trakcie referatu zostaną zaprezentowane tego rodzaju algorytmy dla dwóch klas grafów: bez byka i bez S(1, 1, 2) oraz bez byka i bez S(1, 2, 2). | ||
| 13.11.2024 | Hubert Grochowski | PW |
| Problem przycinania bambusów w ogrodzie | ||
| \(\quad\)Wyobraźmy sobie ogród, w którym rośnie N bambusów (ponumerowanych kolejno od 1 do N) takich, że i-ty bambus rośnie na koniec dnia o wysokość h_i > 0. W ogrodzie mieszka też robotyczna panda, która każdego dnia wybiera jeden bambus i obcina go do zera. Naszym celem jest zaprojektować taki harmonogram strzyżenia dla pandy, aby najwyższy bambus, jaki kiedykolwiek pojawi się w ogrodzie, był jak najniższy. Problem ten został postawiony w literaturze w 2017 przez Gąsieńca i innych [1]. W trakcie referatu omówię ten problem, przedstawię algorytmy aproksymacyjne i wskażę możliwe kierunki badań. [1] Gąsieniec, L., Klasing, R., Levcopoulos, C., Lingas, A., Min, J., & Radzik, T. (2017). Bamboo Garden Trimming Problem (Perpetual Maintenance of Machines with Different Attendance Urgency Factors). In Lecture Notes in Computer Science (pp. 229–240). Springer International Publishing. https://doi.org/10.1007/978-3-319-51963-0_18 | ||
| 6.11.2024 | Seminarium odwołane. | |
| 30.10.2024 | Marta Piecyk | PW |
| Homomorfizmy grafów o ograniczonej średnicy | ||
| \(\quad\)Dla ustalonego grafu H, w problemie homomorfizmu grafów, ozn. Hom(H), mamy dany graf G i pytamy, czy istnieje funkcja f: V(G) -> V(H), która zachowuje krawędzie. Jeśli H jest trójkątem, to Hom(H) jest równoważny z problemem 3-kolorowania. Nie jest wiadomo, czy istnieje wielomianowy algorytm dla 3-kolorowania grafów o średnicy dwa. \(\quad\)Podczas referatu będę rozważać problem Hom(C_{2k+1}) w grafach o ograniczonej średnicy dla k>=2, czyli w przypadku wszystkich nieparzystych cykli innych niż trójkąt. Pokażę wielomianowy algorytm dla Hom(C_{2k+1}) dla grafów o średnicy k+1 -- taki wynik w przypadku k=1 byłby dokładnie wielomianowym algorytmem dla 3-kolorowania grafów o średnicy 2. | ||
| 23.10.2024 | Paweł Rzążewski | PW |
| An 11/6-Approximation Algorithm for Vertex Cover on String Graphs | ||
| \(\quad\)We present a 1.8334-approximation algorithm for Vertex Cover on string graphs given with a representation, which takes polynomial time in the size of the representation; the exact approximation factor is 11/6. Recently, the barrier of 2 was broken by Lokshtanov et al. [SoGC '24] with a 1.9999-approximation algorithm. Thus we increase by three orders of magnitude the distance of the approximation ratio to the trivial bound of 2. Our algorithm is very simple. The intricacies reside in its analysis, where we mainly establish that string graphs without odd cycles of length at most 11 are 8-colorable. Previously, Chudnovsky, Scott, and Seymour [JCTB '21] showed that string graphs without odd cycles of length at most 7 are 80-colorable, and string graphs without odd cycles of length at most 5 have bounded chromatic number. The talk is based on joint work with Édouard Bonnet. | ||
| 16.10.2024 | Tara Abrishami | University of Hamburg |
| Locally chordal graphs | ||
| \(\quad\)In this talk, I will discuss recent results concerning graphs which behave locally like chordal graphs. A graph is chordal if each of its cycles of length at least four has a chord. Chordal graphs have strong structural properties and many equivalent characterizations. They also have algorithmic applications, for example to the maximum independent set problem. The question we aim to answer is: what can we say about graphs which are locally, but not globally, chordal? First, we will discuss three candidate definitions for locally chordal graphs. Next, we will explain local generalizations of two characterizations of chordal graphs: that chordal graphs are intersection graphs of subtrees of a tree, and that chordal graphs are graphs with tree-decompositions into maximal cliques. Finally, we will look at algorithmic applications of locally chordal graphs. This talk is based on joint work with Raphael Jacobs, Paul Knappe, Jonas Kobler, and Jakob Stegemann. | ||
| 9.10.2024 | Konstanty Junosza-Szaniawski | PW |
| O minimalizacji kliki przecięć tras w routingu na cyklu | ||
| \(\quad\)Dla cyklu i listy żądań czyli par jego wierzchołków szukamy wyboru ścieżek łączących wierzchołki z żądań, tak aby zminimalizować rozmiar najliczniejszej kliki w grafie przecięć wybranych ścieżek. Opowiem o złożoności tego problemu, przedstawię prosty kombinatoryczny algorytm 2-approksymacyjny oraz 3/2-aproksymacyjny oparty na programowaniu liniowym. Referat będzie oparty o pracę [1] i myślę że potrwa krócej niż zwykle. [1] Stamati Stefanakos and Thomas Erlebach. Routing in all-optical ring networks revisited. Proceedings. ISCC 2004. Ninth International Symposium on Computers and Communications, volume 1, 288–293, 2004 | ||
| 2.10.2024 | Monika Pilśniak | AGH |
| The Unfriendly Partition Conjecture holds for line graphs | ||
| \(\quad\)A colouring of edges of a graph \(G\) is a majority colouring, if for every vertex \(v\) of \(G\), at most half the edges incident with \(v\) have the same colour. This concept was recently introduced in [1], where, among others, it was proved that every finite graph without pendant vertices admits a majority 4-edge colouring. Moreover, if the minimum degree of \(G\) is at least 4, then \(G\) admits a majority 3-edge colouring. \(\quad\)In the talk, the list version of the problem is investigated, also for infinite graphs. As a consequence of our results, the Unfriendly Partition Conjecture (cf. Diestel's book) is confirmed for line graphs. [1] F. Bock, R. Kalinowski, J. Pardey, M. Pilśniak, D. Rautenbach, and M.Woźniak, Majority Edge-Colorings of Graphs, Electron. J. Combin. 30(1) 2023 #P1.42. | ||