Strona główna > Archiwalny program seminarium > 2021/2022
2021/2022
01.06
Bartłomiej Pawlik
Schinzel, kombinatoryka i grafy
Streszczenie:
Podczas przeglądowego referatu pokazane zostaną przykłady powiązań działalności naukowej prof. Andrzeja Schinzla (1937-2021) z zagadnieniami z zakresu kombinatoryki i teorii grafów.
25.05
Konstanty Junosza-Szaniawski
Liczba Ramseya dla rodzin grafów
Streszczenie:
Liczbą Ramseya R_k(G) nazywamy najmniejsze n takie że dla dowolnego pokolorowanie krawędzi grafu pełnego o n wierzchołkach na k kolorów istnieje monochromatyczna kopia grafu G. Za pracą Ahoriego i in. [1] rozważamy uogólnienie tego pojęcia: dla rodziny grafów F przez R_k(G) oznaczamy najmniejsze n takie że dla dowolnego pokolorowania krawędzi grafu pełnego o n wierzchołkach na k kolorów istnieje monochromatyczna kopia pewnego grafu G należącego do rodziny F. Podamy wartości liczby Ramseya dla rodziny wszystkich cykli, rodziny cykli nieparzystych oraz pewnie ograniczenia na liczbę Ramseya dla rodziny cykli parzystych, rodziny cykli długości ograniczonej od dołu, rodziny skojarzeń i gwiazd.
[1] R.Aharoni, N.Alon, M.Amir, P.Haxell, D.Hefetz, Z.Jiang, G.Kronenberg, A.Naor, Ramsey-nice families of graphs, European Journal of Combinatorics, Volume 72, 2018 pp. 29-44.
18.05 (seminarium zdalne)
Václav Blažej
Games on graphs
Abstract:
We shall present several game theoretic problems on graphs which stem from classical combinatorial problems. Games on graphs are usually (NP/PSPACE/EXPTIME) hard, as the graph structure gives rise to high complexity. To tackle these problems we may employ methods used for tackling classical problems, e.g., restricting the problem to a graph class or to analyze the problem using parameterized complexity. Our focus will be on Online Ramsey theory, Eternal domination, and group identification problem.
11.05
Zbigniew Lonc
Lemat Spernera a sprawiedliwe dzielenie dóbr
Streszczenie:
Podczas referatu pokazane zostaną przykłady wykorzystania lematu Spernera do rozwiązania pewnych problemów sprawiedliwych podziałów dóbr.
27.04
Konstanty Junosza-Szaniawski
Minimalizacja formuł logicznych i jej zastosowania w kryptografii
Streszczenie:
W algorytmie szyfrowania AES jednym z kroków jest przekształcenie liniowe nad ciałem GF(2). Przekształcenie to można przedstawić jako zestaw formuł logicznych, na ogół na wiele sposobów. Im krótsze są to formuły tym łatwiej solverowi programowania logicznego złamać szyfr. W szczególnym przypadku (tzn streight line program) problem zestawu najkrótszych formuł jest problemem NP-Zupełnym [1]. Ponadto przedstawię uogólnienie tego problemu oraz kombinatorykę, która się w nim kryje.
[1] Boyar, J., Matthews, P. & Peralta, R. Logic Minimization Techniques with Applications to Cryptology. J Cryptol 26, 280–312 (2013). https://doi.org/10.1007/s00145-012-9124-7
13.04 (seminarium zdalne)
Andrzej Kisielewicz
Hipoteza Kellera i okolice
06.04 (seminarium zdalne)
Andrzej Grzesik
Uogólniony problem Turána dla cykli
Streszczenie:
Uogólniony problem Turána polega na znalezieniu największej możliwej liczby kopii grafu H w n-wierzchołkowym grafie nie zawierającym grafu F jako podgrafu. Na wykładzie omówimy ten problem w przypadku gdy zarówno graf H jak i F są cyklami. Przedstawimy znane oszacowania i najnowsze rezultaty, w szczególności pierwsze dokładne wyniki w przypadku rzadkim.
30.03 (seminarium zdalne)
Elżbieta Sidorowicz
Właściwa spójność digrafów
23.03 (seminarium zdalne)
Jakub Przybyło
Hipoteza 1-2-3 - 1, 2, 3 nowości
Streszczenie:
Słynna Hipoteza 1-2-3 sugeruje, iż krawędziom dowolnego grafu bez składowej K2 można nadać wagi ze zbioru {1, 2, 3} tak, by sąsiednie wierzchołki
otrzymały różne tzw. ważone stopnie. Problem ten pozostaje nierozwiązany w pełnej rozciągłości. W ramach referatu omówię aktualny stan wiedzy na temat owego zagadnienia oraz postaram się zaprezentować koncepcje, na bazie których zostały poczynione pewne postępy w badaniach dotyczących hipotezy 1-2-3.
16.03 (seminarium zdalne)
Zofia Miechowicz
Matroid Catalana
Streszczenie:
Mogłoby się wydawać, że liczby Catalana są dogłębnie przebadaną strukturą i trudno na ich bazie zbudować nowe, ekscytujące pola dla badaczy. Nic bardziej mylnego! W swoim referacie postaram się zadać kłam tym twierdzeniom. Przedstawię mianowicie matroid Catalana zaproponowany przez F. Ardilę w pracy "The Catalan matroid". Wprowadzę definicję oraz opiszę strukturę tego matroidu, a zapoczątkowane przez F. Ardilę badania jego własności przeniosę na nowe pola, prezentując szereg ciekawych obserwacji i jeszcze więcej pytań otwartych. Podam również szerszy kontekst zagadnienia rozpatrując matroid Catalana jako matroid przesunięć i zwrócę uwagę na związki tych struktur z hipergrafami przesunięć.
09.03
Maria Chudnovsky
Induced subgraphs and tree decompositions
Abstract:
Tree decompositions are a powerful tool in structural graph theory; they are traditionally used in the context of forbidden graph minors. Connecting tree decompositions and forbidden induced subgraphs has until recently remained out of reach.
Tree decompositions are closely related to the existence of "laminar collections of separations" in a graph, which roughly means that the separations in the collection "cooperate'' with each other, and the pieces that are obtained when the graph is simultaneously decomposed by all the separations in the collection "line up'' to form a tree structure. Such collections of separations come up naturally in the context of forbidden minors.
In the case of families where induced subgraphs are excluded, while there are often natural separations, they are usually very far from forming a laminar collection. However, under certain circumstances, these collections of natural separations can be partitioned into a small number of laminar collections (in this context "small" means either constant or logarithmic in the number of vertices of the graph). This in turn allows us to obtain a wide variety of structural and algorithmic results, which we will discuss in this talk.
02.03 (seminarium zdalne)
Jakub Kozik
Orientacje Thomassena
Streszczenie:
Jednym z piękniejszych wyników teorii grafów jest dowód Thomassena mówiący o tym, że każdy graf planarny można pokolorować z list o długości 5.
W roku 2018 Zhu przedstawił znaczne wzmocnienie powyższego twierdzenia dowodząc że liczba Alon-Tarsi dowolnego grafu planarnego nie przekracza 5.
W referacie przedstawię technikę powielania krawędzi, która pozwala łatwo uzyskać powyższy wniosek z nieznacznie zmodyfikowanego dowodu Thomassena. Opowiem również o tym jak klasyczne wyniki Schnydera o dekompozycji grafów planarnych na lasy pozwalają uzyskać jeszcze jeden dowód powyższego faktu. Jak się okazuje dowód ten jest tylko pozornie inny od dowodu Thomassena.
23.02 (seminarium zdalne)
Adam Tyc
Problem kodów Gaussa na płaszczyźnie
Streszczenie:
Abstrakcyjnym kodem Gaussa nazywamy słowo, w którym każdy symbol pojawia się dokładnie dwa razy. Mówimy, że abstrakcyjny kod Gaussa realizuje się, gdy można go otrzymać jako rzut zamkniętej krzywej na płaszczyznę.
W referacie przedstawię warunek konieczny i dostateczny na realizację abstrakcyjnego kodu Gaussa.
Materiał źródłowy: Godsil C., Royle G., Algebraic Graph Theory (2001).
26.01
Konstanty Junosza-Szaniawski
Jeszcze szybszy algorytm zliczający zbiory niezależne w grafie w pamięci wielomianowej
Streszczenie:
W referacie przedstawię obecnie najszybszy znany algorytm do zliczania zbiorów niezależnych w grafie działający w czasie O(1.2330^n ) i w pamięci wielomianowej. Główna idea algorytmu polega na zastosowaniu metody dziel-mierz-zwyciężaj dla grafów subkubicznych w których wierzchołki stopnia 3 nie sąsiadują ze sobą. Algorytm został przedstawiony przez Serge Gaspers, Edward Lee https://arxiv.org/abs/1607.06201. Poprzedni najszybszy algorytm autorstwa KJS i M.Tuczyński działał w czasie O(1.2369^n).
18.01
Mirosław Truszczyński
Preference Orders on Families of Sets—When Can Impossibility Results Be Avoided?
Streszczenie:
Lifting a preference order on elements of some universe to a preference order on subsets of this universe is often guided by postulated properties the lifted order should have. Well-known impossibility results pose severe limits on when such liftings exist if all non-empty subsets of the universe are to be ordered. The extent to which these negative results carry over to other families of sets is not known. In this talk, we consider families of sets that induce connected subgraphs in graphs. For such families, common in applications, we study whether lifted orders satisfying the well-studied axioms of dominance and (strict) independence exist for every or, in another setting, for some underlying order on elements (strong and weak orderability). We characterize families that are strongly and weakly orderable under dominance and strict independence, and obtain a tight bound on the class of families that are strongly orderable under dominance and independence.
Authors: Jan Maly, Mirek Truszczynski, Stefan Woltran
22.12
Michał Dębski
Zliczanie zamiast kompresji entropii
Streszczenie:
Celem referatu jest pokazanie, w jaki sposób można zastąpić metodę kompresji entropii prostym zliczaniem. Pomysł, o którym opowiem, należy do M. Rosenfelda i jest zawarty w jego pracy "Another Approach to Non-Repetitive Colorings of Graphs of Bounded Degree" (Electronic Journal of Combinatorics 27(3), P3.43, 2020, https://doi.org/10.37236/9667).
15.12
Mariusz Zając
O pewnym problemie Steinhausa
Streszczenie:
Jeśli potniemy pręt długości 7m na siedem metrowych odcinków, a potem okaże się, że potrzebujemy jednak ośmiu kawałków równej długości, to mamy problem: musimy zatrudnić spawacza lub zmarnować prawie połowę materiału. Gdybyśmy jednak zgodzili się na odcinki zbliżonej długości zamiast dokładnie równych, pojawiłyby się nowe możliwości, dużo ciekawych pytań i nieco mniej odpowiedzi. Podobne zagadnienia badali w przeszłości m.in. H. Steinhaus, A. Schinzel, P. Erdős, R. Graham, a ostatnio pewien postęp osiągnęli wspólnie M. Anholcer, B. Bosek, J. Grytczuk, G. Gutowski, J. Przybyło, R. Pyzik i wyżej podpisany M. Zając.
08.12
Jarosław Grytczuk
Problem czterech liter
Streszczenie:
Przedstawię kilka zagadnień, w których pojawiają się - czasem nieoczekiwanie - słowa zbudowane z czterech liter. Sztandarowym przykładem jest tu słynny problem kolorowania mapy, który można wyrazić na wiele sposobów w języku kombinatoryki na słowach. Będzie więc mowa o słowach kartezjańskich i anagramach, ale także o trójkącie Conwaya i skośnych bliźniakach oraz ich tajemniczym związku z hipotezą Frankla o szczęśliwym punkcie w rodzinach zbiorów zamkniętych na sumę. Albo o czymś zupełnie innym…
01.12
Jarosław Grytczuk
Bliźniaki w permutacjach
Streszczenie:
Dwa rozłączne podciągi w permutacji, mające ten sam porządek wyrazów, nazywamy bliźniakami. Na przykład, permutacja 15487236 zawiera parę bliźniaków 583 i 472. Jak długie bliźniaki znajdziemy w każdej permutacji długości n? Opowiem co wiemy, a czego nie wiemy o tym problemie i jego wybranych wariantach. Zarysuję także dwa nowe kierunki powiązane z teorią grafów i teorią liczb.
24.11
Karol Matyjanowski
Większościowe kolorowanie digrafów
Streszczenie:
Kolorowanie grafu skierowanego nazywamy większościowym, jeżeli każdy wierzchołek tego digrafu różni się kolorem od co najmniej połowy swoich wychodzących sąsiadów. Tego rodzaju kolorowanie zostało zdefiniowane w 2016 roku przez van der Zypena i stanowi skierowany analog dla nieprzyjaznego kolorowania grafów prostych, w którym to każdy wierzchołek otrzymuje kolor różny od co najmniej połowy swoich sąsiadów. Już w latach 60 odkryto, że wszystkie grafy proste są 2-kolorowalne nieprzyjaźnie. Obecnie wiadomo też, że wszystkie digrafy są 4-wybierlane większościowo oraz, że digrafy bez skierowanych cykli nieparzystej długości są 2-wybieralne większościowo. Oba zagadnienia kolorowania nieprzyjaznego i większościowego mają oczywiście swoje odpowiedniki dla grafów nieskończonych, w tym też, w szczególności, dla grafów borelowskich. W trakcie referatu omówię metody stosowane dla skończonych grafów i digrafów oraz pokażę adaptacje tych metod dla przypadków borelowskich.
17.11
Szymon Tur
O 2-dystansowym kolorowaniu grafów planarnych i metodzie rozładowywania
Streszczenie:
2-dystansowym kolorowaniem grafu nazywamy poprawne kolorowanie kwadratu tego grafu, tj. takie, w którym zarówno wierzchołki sąsiadujące, jak i mające wspólnego sąsiada, otrzymają różne kolory. Znamy ścisłe ograniczenie górne na liczbę kolorów, którymi można "klasycznie" pokolorować graf planarny, lecz dla 2-dystansowego kolorowania problem jest otwarty już dla grafów o maksymalnym stopniu Δ(G)>=4. W trakcie referatu przedstawię znane ograniczenia górne dla różnych wartości Δ(G) oraz omówię metodę rozładowywania, znaną m. in. ze słynnego Twierdzenia o Czterech Kolorach, która posłużyła do pokazania nowego ograniczenia górnego dla grafów o Δ(G)>=6.
Praca wspólna z Mateuszem Krzyzińskim i Pawłem Rzążewskim.
03.11
Tomasz Krawczyk
Własność Helly'ego w grafach łukowych
Streszczenie:
Grafy łukowe, definiowane jako grafy przecięć łuków ustalonego okręgu, są jedną z najprostszych klas grafów przecięć, która w ogólności nie spełnia własności Helly'ego (tzn. istnieją grafy łukowe, w których pewne kliki mogą być reprezentowane przez parami przecinające się łuki o pustym wspólnym przecięciu). W szczególności, niektóre kliki grafu łukowego mogą spełniać własność Helly'ego w pewnych, ale niekoniecznie wszystkich reprezentacjach grafu łukowego.
W problemie klik Helly'ego, dla zadanych na wejściu grafu łukowego G oraz klik C1,...,Ck (niekoniecznie maksymalnych) w G pytamy, czy istnieje reprezentacja łukowa G, w której wszystkie kliki C1,...,Ck spełniają własność Helly'ego. Wiadomo jest, że problem klik Helly'ego jest NP-zupełny i że, przy założeniu hipotezy ETH, nie można go rozwiązać w czasie 2^{o(k)}poly(n), gdzie n jest liczbą wierzchołków grafu G (Ağaoğlu i inni). W naszym referacie przyjrzymy się problemowi klik Helly'ego w kontekście złożoności parametryzowanej, gdzie naturalnym parametrem jest liczba klik podanych na wejściu. Pokażemy mianowicie, że problem klik Helly'ego:
• ma algorytm o czasie działania 2^{O(k log k)}poly(n) (a więc należy do klasy FPT),
• ma algorytm kernelizacji konstruujący jądro rozmiaru O(k^6 ).
Ponadto, omówimy relacje problemu klik Helly'ego z problemami rozpoznawania tzw. H-grafów, w szczególności w kontekście tych grafów H, dla których problem ten pozostaje otwarty.
Praca wspólna z Janem Derbiszem. Część wyników omawianych w referacie jest wspólna z Deniz Ağaoğlu, Onurem Çağricim, Janem Derbiszem, Timem Hartmannem, Petrem Hliněným, Janem Kratochvílem oraz Peterem Zemanem.
27.10
Paweł Rzążewski
Grafy P5-wolne są quasiwielomianowo chi-ograniczone
Streszczenie:
Klasyczny wynik Gyarfasa pokazuje, że grafy bez indukowanych ścieżek o t wierzchołkach (Pt-wolne) są chi-ograniczone, a funkcja ograniczająca jest wykładnicza względem w. Pomimo licznych prób i głębokiej wiary, jak dotąd nie udało się pokazać, że grafy Pt-wolne są wielomianowo chi-ograniczone. Problem ten jest otwarty już dla t=5.
Niedawno Scott, Seymour i Spirkl pokazali, że dla grafów P5-wolnych funkcja ograniczająca jest ograniczona przed quasiwielomian, tj. f(w) <= w^log w [1].W ramach referatu przedstawię ten wynik i jego piękny dowód.
[1] Scott, Seymour, Spirkl, Polynomial bounds for chromatic number. IV. A near-polynomial bound for excluding the five-vertex path. Dostępne online: https://web.math.princeton.edu/~pds/papers/poly4/paper.pdf
20.10
Karolina Okrasa
Zbalansowane separatory w dziedzicznych klasach grafów
Streszczenie:
Niech S będzie podzbiorem V(G) i niech 0 < α < 1. Powiemy że S jest α-zbalansowanym separatorem, jeśli każda spójna składowa grafu G-S ma rozmiar co najwyżej α|V(G)|. Klasa grafów C jest dziedziczna, jeśli jest zamknięta na branie indukowanych podgrafów.
Niech C będzie dziedziczną klasą grafów. Załóżmy, każdy graf G z C posiada α-zbalansowany separator rozmiaru O(Δ(G)), gdzie Δ(G) oznacza największy stopień wierzchołka w G. Podczas referatu omówię, jakie znane nam dziedziczne klasy grafów mają tę własność, oraz zademonstruję, w jaki sposób możemy dzięki temu projektować algorytmy podwykładnicze (dla problemu homomorfizmu grafów, ale nie tylko).
Praca wspólna z Pawłem Rzążewskim.
13.10
Marta Piecyk
3-kolorowanie grafów o ograniczonej średnicy
Streszczenie:
Problem 3-kolorowania grafów jest NP-trudny, a zakładając pewną hipotezę z teorii złożoności (ETH), nie istnieje algorytm, który rozwiązywałby 3-kolorowanie w czasie podwykładniczym. To dolne ograniczenie zachodzi nawet, jeśli ograniczymy się do grafów o średnicy co najwyżej 4. W 2013, Mertzios i Spirakis badali ten problem dla grafów o średnicy 2 i 3 - pokazali, że dla grafów o średnicy 3 problem jest NP-trudny, a dla grafów o średnicy 2 przedstawili algorytm o złożoności 2^O(sqrt(n log n)). Nie wiemy jednak, czy 3-kolorowanie grafów o średnicy 2 da się rozwiązać w czasie wielomianowym.
W trakcie referatu przedstawię algorytm dla 3-kolorowania grafów o średnicy 2 o złożoności 2^O(n^1/3 log^2 n).
Są to wyniki uzyskane wspólnie z Michałem Dębskim i Pawłem Rzążewskim.