Aktualny program seminarium
Jeśli chcesz otrzymywać regularnie aktualny plan referatów, to napisz do sekretarza seminarium.
| 17.12.2025 (102) | Maria Chudnovsky | Princeton University |
| Strip Structures: past and present | ||
| \(\quad\)An independent set S of vertices is "constricted" in a graph G if no induced tree in G contains 3 elements of S. In 2009 Paul Seymour and the speaker proved a theorem describing the structure of constricted sets in graphs. It turns out that if a graph G contains a constricted set Z, then G admits a "strip structure", which is to say that it roughly resembles a line graph. Moreover, the location of the vertices of Z is tightly controlled. This result is called "3-In-A-Tree". \(\quad\)The original motivation behind 3-In-A-Tree was to provide a recognition algorithm for induced thetas in graphs, but recently it has been reincarnated. In modern graph optimization algorithms it is used to produce small dominating sets in graphs, or to allow for other ways to track the progress of an algorithm. \(\quad\)In this talk we will explain the theorem, and illustrate some of its applications. | ||
Archiwalny program seminarium (rok akademicki 2025/2026)
| 10.12.2025 | Tomasz Kościuszko | UAM |
| Zbiór popularnych sum i jego zastosowania w kombinatorycznej teorii liczb | ||
| \(\quad\)Motywem przewodnim referatu będzie zbiór popularnych sum pewnego skończonego podzbioru liczb naturalnych \(A\). Każdy element ze zbioru wszystkich sum \(A+A\) można wyrazić jako sumę dwóch liczb z \(A\) na średnio \(\frac{|A|^2}{|A+A|}\) sposobów. Popularne sumy to takie, które przekraczają ten próg (pomnożony przez wybraną małą stałą): \(P = \Bigl\{s\in A+A : 1_A*1_A(s)\geq \frac{|A|^2}{10\cdot |A+A|}\Bigr\}.\) Tutaj \(1_A*1_A(s)\) oznacza splot, czyli dokładnie liczbę par \((a,b)\in A\times A\) sumujących się do \(s\). \(\quad\)Wspomnimy o wyniku Sandersa [1], który mówi że w zbiorze popularnych sum można znaleźć ciekawe struktury takie jak ciągi arytmetyczne czy zbiory Bohra (tam musimy rozważać popularne sumy w \(A+A+A+A\)). Budując na tym przedstawimy wynik autora [2], który pozwala na znalezienie wielu rozwiązań równań liniowych w gęstych zbiorach liczb. Jeśli czas pozwoli opiszemy również inne kombinatoryczne zastosowania. [1] T. Sanders, On the Bogolyubov–Ruzsa lemma. Anal. PDE 5 (3) 627 - 655, 2012. [2] _, Invariant Equations in Many Variables. Electronic Journal of Combinatorics, Volume 32, Issue 3 (2025) | ||
| 26.11.2025 | Przemysław Gordinowicz | Politechnika Łódzka |
| Dominacyjna liczba drzewiasta | ||
| \(\quad\)Przedmiotem referatu są dekompozycje drzewiaste w których wielkość worka (bagu) opisywana jest przez liczbę dominującą odpowiedniego podgrafu. Pokazany zostanie opis przez rozgrywane przeszukiwaniem grafów oraz związek tytułowego parametru z drzewiastą dekompozycją hipergrafów. Oraz całkiem sporo problemów czekających na rozwiązanie. | ||
| 19.11.2025 | Paweł Rzążewski | PW |
| Problem zbioru niezależnego w grafach uporządkowanych, c.d. | ||
| \(\quad\)Kontynuujemy rozważania na temat problemu największego zbioru niezależnego w klasach grafów uporządkowanych z wykluczonym ustalonym podgrafem indukowanym. Tym razem skupimy się na algorytmach. Wyniki uzyskane we współpracy z Pawłem Rafałem Bielińskim i Martą Piecyk. | ||
| 12.11.2025 | Paweł Rafał Bieliński | PW |
| KTGiZU na kółku matematycznym | ||
| \(\quad\)Zaprezentuję garść problemów z olimpiad matematycznych szczebla międzynarodowego. Ich wspólną cechą jest (nieraz dość błyskotliwe) wykorzystanie metod K, TG i ZU. Przedstawię również klasyczne twierdzenie Steinitza, które wiąże zbiór niezależny w grafie z możliwością wpisania wielościanu w sferę. | ||
| 29.10.2025 | Seminarium odwołane |
| 22.10.2025 | Hubert Grochowski | PW |
| Grafy XOR-magiczne | ||
| \(\quad\) Graf \(G\) o \(2^n\) wierzchołkach nazwiemy grafem otwarcie (domknięcie) XOR-magicznym, jeśli jest spójny i istnieje bijekcja ze zbioru wierzchołków grafu G w zbiór ciągów binarnych długości n taka, że dla każdego wierzchołka tego grafu, suma etykiet wierzchołków w jego otwartym (domkniętym) sąsiedztwie jest równa wektorowi zerowemu. \(\quad\)W jednej z prac dotyczących tego tematu [1], Batal badał problem istnienia regularnych grafów XOR-magicznych. W szczególności, postawił on problem otwarty: czy istnieje graf nieparzyście (parzyście) regularny graf otwarcie (domknięcie) XOR-magiczny? \(\quad\)W trakcie referatu odpowiemy pozytywnie na wyżej wymieniony problem, pokazując istnienie takich grafów rzędu \(2^n\) dla każdego \(n\) większego od 3. Ponadto, przedstawimy warunek konieczny (w nurcie spektralnej teorii grafów) istnienia grafów otwarcie XOR-magicznych wraz z jego zastosowaniami do wybranych grafów Cayleya. \(\quad\)Współautorki: Sylwia Cichacz, Rita Zuazua [1] A. Batal, On the construction of XOR-magic graphs, Discrete Applied Mathematics 379 (2026), 288-315. | ||
| 15.10.2025 | Tomasz Krawczyk | PW |
| Problem Defensywnej Dominacji w klasie grafów przedziałowych | ||
| \(\quad\)W problemie Defensywnej Dominacji dla danego grafu G oraz liczb naturalnych l i k należy rozstrzygnąć, czy na wierzchołkach grafu G można rozmieścić l obrońców w taki sposób, aby chronili oni przed atakiem każdy podzbiór A wierzchołków o rozmiarze co najwyżej k (tzn. każdemu wierzchołkowi z atakowanego zbioru A można przypisać prywatnego obrońcę znajdującego się w tym wierzchołku lub w jego sąsiedztwie). Wiadomo, że problem Defensywnej Dominacji jest \(\Sigma_2^P\)-zupełny. Niestety, nie jest znany jego status złożonościowy w prostych klasach grafów, takich jak grafy przedziałowe czy grafy planarne. W swoim referacie przedstawię prosty algorytm zachłanny rozwiązujący problem Defensywnej Dominacji w klasie grafów przedziałowych w przypadku, gdy w każdym wierzchołku grafu można umieścić dowolną liczbę obrońców. Pokażę również, jaki związek zachodzi między klasycznym problemem Defensywnej Dominacji (co najwyżej jeden obrońca na wierzchołek) a problemem plecakowym. | ||
| 08.10.2025 | Paweł Rafał Bieliński | PW |
| Problem zbioru niezależnego w grafach uporządkowanych | ||
| \(\quad\)Wiele trudnych problemów algorytmicznych może być rozwiązane wydajniej w węższym zakresie sytuacji. Przykładem takiego podejścia jest rozważanie nie grafów dowolnych, ale tylko tych nie zawierających określonej podstruktury. W swoim referacie zaprezentuję wyniki dotyczące trudności problemu zbioru niezależnego w klasach grafów uporządkowanych wolnych od określonych podgrafów indukowanych. Przy pomocy odpowiednich redukcji wskażę szereg przypadków NP-trudnych, a poprzez konkretne algorytmy i wnioski strukturalne zidentyfikuję przypadki, które można rozwiązać w czasie wielomianowym. | ||