Strona główna > Aktualny program seminarium
Aktualny program seminarium
Jeśli chcesz otrzymywać regularnie aktualny plan referatów to napisz do sekretarza seminarium.
17.04
Sesja problemowa
24.04
08.05
Barbara Nayar
szczegóły wkrótce
15.05
seminarium odwołane (piątek na PW)
22.05
29.05
05.06
12.06
Poprzednie referaty (rok akademicki 2023/2024):
10.04
Paweł Rzążewski
Dekompozycje drzewiaste i skojarzenia indukowane: Yolov-width II.
Streszczenie:
Dla dekompozycji drzewiastej T grafu G, przez μ(T) oznaczamy rozmiar największego skojarzenia indukowanego, którego każda krawędź przecina ustalony wór (bag) dekompozycji. Przez tree-μ(G) oznaczamy najmniejszą wartość μ(T) po wszystkich dekompozycjach T grafu G.
Pokażę dwie własności strukturalne grafów o ograniczonym parametrze tree-μ(G):
- Grafy o ograniczonym parametrze tree-μ, które nie zawierają ustalonej bikliki jako podgrafu indukowanego, mają ograniczony parametr tree-independence.
- Grafy o ograniczonym parametrze tree-μ są klasą χ-ograniczoną.
Przedstawione wyniki są uzyskane we współpracy z T. Abrishami, M. Briańskim J. Czyżewską, R. McCarty, M. Milaničem i B. Walczakiem.
03.04
Paweł Rzążewski
Dekompozycje drzewiaste i skojarzenia indukowane: Yolov-width I.
Streszczenie:
Dla dekompozycji drzewiastej T grafu G, przez μ(T) oznaczamy rozmiar największego skojarzenia indukowanego, którego każda krawędź przecina ustalony wór (bag) dekompozycji. Przez tree-μ(G) oznaczamy najmniejszą wartość μ(T) po wszystkich dekompozycjach T grafu G. Yolov [SODA 2018] pokazał, że problem największego zbioru niezależnego da się rozwiązać w czasie wielomianowym dla grafów o stałym parametrze tree-μ(G). W trakcie referatu pokażę, że w czasie wielomianowym można też rozwiązać problem Feedback Vertex Set, czyli problem znalezienia najmniejszego zbioru przecinającego wszystkie cykle.
Jeśli starczy czasu, opowiem też o własnościach strukturalnych tego parametru (a jeśli nie, to może innym razem). Referat jest oparty na pracy https://arxiv.org/abs/2402.15834
27.03
Michał Dębski
O unikaniu tangramów raz jeszcze
Streszczenie:
Tangramem o liczbie cięciowej k nazywamy słowo, które można rozciąć w k miejscach tak, żeby z powstałych fragmentów dało się ułożyć dwa identyczne słowa. Przez t(k) oznaczamy minimalny rozmiar alfabetu, nad którym istnieją dowolnie długie słowa unikające tangramów o liczbie cięciowej co najwyżej k.
Od niedawna wiadomo, że t(k) nie przekracza k+1 dla wszystkich k większych niż 3. Okazuje się jednak, że prawdziwa jest dużo silniejsza (dla dużych k) nierówność t(k)<1024(log k + log log k).
20.03
Jakub Żuchowski
Grafy bez podgrafów 3-spójnych są 4-kolorowalne
Streszczenie:
W roku 1972 Mader pokazał, że grafy bez podgrafów 3-spójnych są 4-zdegenerowane, a zatem 5-kolorowalne. Na początku lutego 2024 roku Bonnet, Feghali, Thomassé i Trotignon poprawili to stwierdzenie, dowodząc, że grafy takie są 4-kolorowalne. W moim referacie przedstawię dowód tego stwierdzenia.
06.03
Hubert Grochowski
Cieniowane kolorowanie płaszczyzny i asymptotycznie 6-aproksymacyjny algorytm L(2,1)-etykietowania grafów przecięć dysków jednostkowych
Streszczenie:
L(2,1)-etykietowaniem grafu nazywamy przyporządkowanie wierzchołkom nieujemnych liczb całkowitych (etykiet) tak, aby każde dwa sąsiadujące wierzchołki otrzymały etykiety różniące się o co najmniej 2, a każde dwa wierzchołki w odległość 2 otrzymały różne etykiety. kolei grafem przecięć dysków jednostkowych (UDG) jest graf, dla którego istnieje rodzina dysków na płaszczyźnie o średnicy 1 taka, że każdy wierzchołek możemy utożsamić z jednym z tych dysków w ten sposób, że dwa wierzchołki sąsiadują wtedy, gdy odpowiadające im dyski się przecinają.
Ono i Yamanaka w 2023 zaproponowali, dotychczas najlepszy, 8-aproksymacyjny algorytm dla etykietowania L(2,1) grafów UDG. Zainspirowani ich pracą rozważamy model cieniowanego kolorowania płaszczyzny (i jego wersji warstwowej i ułamkowej) i proponujemy algorytm o asymptotycznym współczynniku aproksymacji mniejszym od 6.
Wyniki wspólne z Konstantym Junoszą-Szaniawskim.
28.02
Sebastian Czerwiński (Uniwersytet Zielonogórski)
O tym jak Grytczuk z Alonem i Grahamem grafy dwudzielne dzielili
Streszczenie:
Graham i Pollak udowodnili, że nie można podzielić zbioru krawędzi kliki na n wierzchołkach na mniej niż n-1 biklik. Rozważamy powiązany problem podziału zbioru krawędzi bikilki na bikliki z dodatkowymi założeniami.
Biklika H=(X, Y) jest podzbiorem właściwym bikliki G=(V, W) jeśli zbiory X i Y są właściwymi podzbiorami odpowiednio V i W. Alon, Bohman, Holzman i Kleitman udowodnili, że jeśli biklika zostanie podzielone na r właściwych bikliki, wówczas r będzie wynosić co najmniej 4.
Przedstawiamy uogólnienie tego twierdzenia. Zakładamy, że mniej niż k podbiklik nie może pokryć zbiorów V i W bikliki G. Przedstawiamy także uogólnienie na hipergrafy.
21.02
Konstanty Junosza-Szaniawski
Dyskretnie o protokołach kryptograficznych
Streszczenie:
W referacie przedstawię podstawowe własności protokołów kryptograficznych, narzędzia do formalnej weryfikacji weryfikacji tychże własności, kilka przykładów klasycznych protokołów oraz przykłady ataków na nie.
24.01
Hoang La
The χ-binding function of d-directional segment graphs
Streszczenie:
To color a graph properly, one needs at least as many colors as the size of its biggest clique; therefore, the chromatic number χ is lower-bounded by the clique number ω. In general, there are no upper bounds on χ in terms of ω. The graphs for which we can approximate the chromatic number with ω ≤ χ ≤ f(ω) for some function f are called χ-bounded graphs and the optimal function f is called the χ-binding function.
A class of graphs that has been the object of many studies in structural graph theory is the class of segment graphs: a segment graph is formed by a collection of straight line segments in the plane where the vertices are the segments and there is an edge between two intersecting segments. If the segments are all parallel, then it is also called an interval graph, known for being perfect (χ = ω). In the 70s, Erdös asked if we allow segments to have different slopes, then can we still approximate χ with ω, i.e. are segment graphs χ-bounded? In 2014, Pawlik, Kozik, Krawczyk, Lasoń, Micek, Trotter, and Walczak showed a construction of a triangle-free graph (ω = 2) with arbitrarily large chromatic number, answering Erdös question in the negative.
However, if one only allows the segments to have d different slopes (d-directional segment graphs), then it is easy to color the graph with dω colors since each slope induces an interval graph. Bhattacharya, Dvorák and Noorizadeh conjectured that dω is optimal, meaning that there exists d-directional segment graphs for which χ = dω for every d and every ω.
In this seminar, we will show the χ-binding function of d-directional segment graphs, which confirms the conjecture for even ω and refutes it for odd ω.
17.01
Adam Mata
Kombinatoryczne aspekty geometrii wypukłych
Streszczenie:
A convex geometry (CG) is a finite closure system with the anti-exchange property known in combinatorics and lattice thoery. Its dual is an antimatroid. As a combinatorial object it may be generated by permutations on a finite set.
In the nineties, a series of papers studied Frattini sublattice, which is an intersection of maximal sublattices in a given lattice, and considerable progress was done in that matter.
In this talk we show some results about maximal sublattices and Frattini sublattice in these classes. In particular, there is full description of maximal sublattices in convex geometries of convex dimension 2.
This is joint work with K. Adaricheva, S. Silberger, and A. Zamojska-Dzienio.
10.01
Konstanty Junosza-Szaniawski
Dyskretnie o kryptografii postkwantowej
Streszczenie:
Obecnie używane szyfry bazują na trudności problemu rozkładu liczb oraz logarytmu dyskretnego. Te problemy nie są wystarczająco trudne dla komputerów kwantowych. Perspektywa powstania komputerów kwantowych zmusza ludzkość do stworzenia nowych szyfrów opartych na problemach, które oprą się komputerom kwantowym. Obecnie najbardziej obiecującymi problemami, na których mogłyby bazować takie szyfry są problemy kratowe (problem najkrótszego wektora, problem najbliższego punktu, problem uczenia z błędami). Przedstawię ideę takich algorytmów, próby ataku oraz jak możemy szacować bezpieczeństwo takich szyfrów, czyli o algorytmice i teorii złożoności, która za tym stoi.
13.12
Jarosław Grytczuk
Rozcinanie tangramów słownych
Streszczenie:
Tangramem nazywamy słowo, w którym każda litera występuje parzystą liczbę razy. Taki tangram można więc rozciąć na części, z których da się utworzyć dwa identyczne słowa. Minimalna liczba cięć potrzebna dla danego tangramu to jego liczba cięciowa. Na przykład, tangramy o liczbie cięciowej 1 to tzw. kwadraty, czyli słowa postaci UU, gdzie U jest dowolnym niepustym słowem.
Niech k będzie ustaloną liczbą naturalną. Niech t(k) oznacza minimalny rozmiar alfabetu, nad którym istnieją dowolnie długie słowa unikające tangramów o liczbie cięciowej nie większej niż k. W roku 1906, Thue udowodnił, że t(1) = 3. Z tego łatwo wynika, że t(2) = 3. Nie wiadomo ile dokładnie wynosi t(3), ani tym bardziej ile jest równe t(k), dla k > 3, ale udało się dowieść, że t(k) nie przekracza k + 1, dla k > 3. Dowód wykorzystuje słynne twierdzenie z kombinatoryki na słowach, znane jako Hipoteza Dejean, a także pewne nowe własności tzw. słów Gaussa.
06.12
Joanna Polcyn (Uniwersytet im. Adama Mickiewicza, Poznań)
Gęste grafy bez trójkątów
Streszczenie:
W roku 1907 Mantel pokazał, że grafem bez trójkątów, który maksymalizuje liczbę krawędzi przy zadanej liczbie wierzchołków jest zbalansowany graf dwudzielny.
W swoim referacie odpowiem na pytanie jak gęste mogą być grafy bez trójkątów, jeśli nałożymy na nie pewne dodatkowe ograniczenia:
- na liczbę chromatyczną, tutaj miarą gęstości będzie minimalny stopień;
- na wielkość największego zbioru niezależnego - jako miarę gęstości przyjmiemy liczbę krawędzi przy zadanej liczbie wierzchołków.
22.11
Tomasz Krawczyk
Proste klasy grafów przecięć - struktura i algorytmy
Streszczenie:
W moim referacie skupię się na dwóch problemach dotyczących algorytmicznych i strukturalnych własności prostych klas grafów przecięć:
- znalezieniu granicy wielomianowej rozwiązywalności dla problemów rozpoznawania H-grafów,
- scharakteryzowaniu minimalnych struktur zabronionych dla klasy grafów łukowych.
Opowiem o ostatnich wynikach w kierunku rozwiązania tych dwóch problemów oraz o problemach otwartych wokół tej tematyki.
16.11
Andrzej Ruciński
Problem Boska ze skarpetkami, czyli największe podskojarzenie dwudzielne w losowym skojarzeniu uporządkowanym
Streszczenie:
Let M be an ordered matching of size n, that is, a partition of the set [2n] into 2-element subsets. The sock number of M is the maximum size of a sub-matching of M in which all left-ends of the edges precede all the right-ends (such matchings are also called bipartite). The name of this parameter comes from an amusing "real-life" problem posed by Bosek, concerning an on-line pairing of randomly picked socks from a drying machine.
Answering one of Bosek's questions we prove that the sock number of a random matching of size n is asymptotically equal to n/2. Moreover, we prove that the expected average number of socks waiting for their match during the whole process is equal to (2n+1)/(6). Analogous results are obtained if socks come not in pairs, but in sets of size at least 2, which corresponds to a similar problem for random ordered r-matchings. We also attempt to enumerate matchings with a given sock number.
This is joint work with Andrzej Dudek and Jarek Grytczuk.
08.11
Paweł Twardowski
Wielomiany grafowe i rozszerzalność kolorowań grafów planarnych
Streszczenie:
Słynne twierdzenie Thomassena mówi w najprostszej postaci, że każdy graf planarny jest 5-wybieralny. Jak jednak wiadomo, na potrzeby kroku indukcyjnego w dowodzie, Thomassen pokazał więcej: że długości list wierzchołków na zewnętrznej ścianie mogą być nie większe od 3, a dwa dowolnie wybrane, sąsiednie, zewnętrzne wierzchołki mogą być prekolorowane. O takiej sytuacji mówimy, że kolorowanie owej pary sąsiednich wierzchołków rozszerza się do listowego kolorowania całego grafu. W 2007 roku Thomassen udowodnił kolejne utrzymane w podobnej konwencji twierdzenie, tym razem podając warunki wystarczające, by można było rozszerzyć kolorowanie nie dwóch, a trzech zewnętrznych wierzchołków tworzących ścieżkę. Z kolei w 2018 Zhu pokazał analog twierdzenia Thomassena wyrażony w języku wielomianów grafowych. W moim wystąpieniu przedstawię wielomianowy analog twierdzenia Thomassena o rozszerzalności ścieżki długości 3, przy okazji prezentując wyniki dotyczące rozszerzalności kolorowań kilku rodzin grafów planarnych, istotnych w kontekście głównego twierdzenia.
25.10
Maria Chudnovsky
Perfect Graphs: an overview
Streszczenie:
A graph is called perfect if for every induced subgraph, the size of its largest clique equals the minimum number of colors needed to color its vertices. As it turns out, the notion of perfect graphs generalizes a large number of phenomena, both in graph theory and in combinatorial optimization. Therefore, the problems of characterizing perfect (or minimal imperfect) graphs and finding an efficient recognition algorithm have become well known in both communities. In the 1960's Claude Berge made a conjecture that any graph with no induced odd cycles of length greater than three or their complements is perfect (thus, odd cycles of length greater than three and their complements are the only minimal imperfect graphs). This conjecture became know as the Strong Perfect Graph Conjecture.
We call graphs containing no induced odd cycles of length greater than three or their complements Berge graphs. A stronger conjecture was made by Conforti, Cornuejols and Vuskovic, that any Berge graph either belongs to one of a few well understood basic classes or has a decomposition that cannot occur in a minimal counterexample to Berge's Conjecture. In joint work with Neil Robertson, Paul Seymour and Robin Thomas we were able to prove this conjecture and consequently the Strong Perfect Graph Theorem.
In my talk I will explain some of the ideas of the proof.
18.10
Jarosław Grytczuk
Kombinatoryczne etiudy-obrazy
Streszczenie:
Opowiem o kilku wybranych problemach otwartych dotyczących rozmaitych struktur kombinatorycznych. Ich wspólną cechą jest specyficzna "obrazowość", a także pewnego rodzaju "dynamika" pozwalająca na sugestywne interpretacje pobudzające wyobraźnię. Z niektórymi wiążą się ciekawe historie, w których występują znane i mniej znane postacie ludzkie.
11.10
Marta Piecyk
Rekonstrukcja grafów
Streszczenie:
W problemie rekonstrukcji, dla ustalonej liczby k i zbioru V, mamy dane T_k, T'_k -- zbiory k-elementowych podzbiorów V -- i chcemy stwierdzić czy istnieje graf G o zbiorze wierzchołków V taki, że dla każdego {v_1,...,v_k} w T_k graf G[{v_1,...,v_k}] jest spójny oraz dla każdego {u_1,...,u_k} w T'_k graf G[{u_1,...,u_k}] jest niespójny. Interesującym pytaniem jest również, kiedy taki graf G jest wyznaczony jednoznacznie. W trakcie referatu opowiem, co wiadomo na temat tego problemu.