Aktualny program seminarium
Jeśli chcesz otrzymywać regularnie aktualny plan referatów, to napisz do sekretarza seminarium.
| 28.10.2026 | Ahmet Batal | Izmir Institute of Technology |
| Algebraic characterizations of generating and affinely generating \(\Gamma\)-magic maps and \(\Gamma\)-distance magic labelings on regular graphs | ||
| \(\quad\)For a finite abelian group \(\Gamma\), a \(\Gamma\)-magic map on a graph \(G\) is a map \(f\colon V(G)\to\Gamma\) with constant open-neighborhood sums. It is generating if its labels generate \(\Gamma\), and affinely generating if their pairwise differences generate \(\Gamma\). Let \(G\) be regular and write \(\Gamma\cong\bigoplus_{i=1}^{r}\mathbb{Z}/d_i\mathbb{Z},\quad d_1\mid\cdots\mid d_r,\quad B_{\Gamma}=\bigoplus_{i=1}^{r-1}\mathbb{Z}/d_i\mathbb{Z},\) with \(B_{\Gamma}=\{0\}\) when \(r=1\). Let \(\overline A_m\) be the endomorphism induced by adjacency on \((\mathbb{Z}/m\mathbb{Z})^{V(G)}\) modulo constant vectors. We prove that \(G\) admits generating and affinely generating \(\Gamma\)-magic maps if and only if, respectively, \(B_{\Gamma}\hookrightarrow\ker\overline A_{d_r}\qquad\text{and}\qquad\Gamma\hookrightarrow\ker\overline A_{d_r}.\) When \(|V(G)|=|\Gamma|\), a bijective \(\Gamma\)-magic map, called a \(\Gamma\)-distance magic labeling, exists precisely when the latter embedding has an image that separates every pair of distinct vertices by a coordinate difference. If the integral reduced adjacency operator is nonsingular over \(\mathbb{Q}\), the first two criteria become subgroup conditions in its cokernel. A graph of order \(n\) is distance magic if it admits a bijection from its vertex set to \(\{1,\ldots,n\}\) with constant open-neighborhood sums. Cichacz and Froncek conjectured that every such graph is \(\Gamma\)-distance magic for every abelian group \(\Gamma\) of order \(n\). We use these characterizations to disprove this conjecture by constructing a \(6\)-regular distance magic graph of order \(27\) with no affinely generating \((\mathbb{Z}/3\mathbb{Z})^3\)-magic map. For Cayley graphs on elementary abelian \(p\)-groups, the same characterizations yield a nonexistence result which, combined with a known sufficient condition, shows that a \(\Gamma\)-distance magic labeling exists over some abelian group \(\Gamma\) of the graph order if and only if the regularity is divisible by \(p\). | ||
| 04.11.2026 | Grzegorz Gutowski | Uniwersytet Jagielloński |
| Szczegóły wkrótce. | ||
Archiwalny program seminarium (rok akademicki 2026/2027)
| 21.10.2026 | Paweł Rafał Bieliński | PW |
| Ramsey pruning | ||
| \(\quad\)Znany jest szereg problemów, dla których decydujące jest pytanie o możliwość uporządkowania wierzchołków grafu tak, by uniknąć określonych konfiguracji (tzw. patterns). Przykładem może być rozpoznanie grafów zewnętrznie planarnych czy cięciwowych. Technika Ramsey pruning pozwala zredukować niektóre tego typu pytania do grafów o rozmiarze ograniczonym przez funkcję parametru \(p\) (tzw. vertex integrity). Okazuje się bowiem, że właściwe uporządkowanie odpowiednio dużego grafu musi zawierać podstrukturę, która pozwala rozszerzyć je na graf dowolnie duży. Nazwa techniki odnosi się właśnie do tego "przycinania" "nieistotnych" kopii pewnych podgrafów. Podczas referatu skupimy się na problemie rozpoznania grafów o ograniczonym stack number oraz queue number, czyli problemie, do którego Ramsey pruning zastosowano po raz pierwszy. Referat oparty jest więc na pracy T. Depiana, S. Finka, R. Ganiana i V. Surianarayanana. | ||
| 14.10.2026 | Hubert Grochowski | PW |
| Najkrótsza ścieżka z atakującym - aspekty złożonościowe i probabilistyczne | ||
| \(\quad\)W problemach praktycznych, nierzadko musimy zmierzyć się z niepewnością danych. Jednym z podejść do modelowania tego typu problemów jest przedstawienie ich jako gry dwuosobowej, gdzie jeden gracz stara się rozwiązać problem, a drugi zaburza dane, symulując ich niepewność. W trakcie referatu, skupimy się na grze typu min-max "Shortest Path under the Attacks", granej na ważonym grafie pomiędzy dwoma graczami - Ścieżkowcem (Pather), który chce wybrać możliwie najtańszą ścieżkę pomiędzy dwoma ustalonymi wierzchołkami i Atakującym (Attacker), który dysponuje budżetem, który może rozdzielić na krawędzie grafu, zwiększając przy tym wagi niektórych z nich. \(\quad\)Szczegółowo skupimy się na wariancie mieszanym tej gry, gdzie gracze szukają optymalnych rozkładów prawdopodobieństwa na przestrzeni swoich ruchów, aby uzyskać optymalny średni wynik gry. Pokażemy, że w pewnych szczególnych przypadkach tej gry, optymalne rozkłady można znaleźć w czasie wielomianowym. Ponadto przedstawimy wyniki probabilistyczne dotyczących struktury optymalnych rozkładów dla Ścieżkowca. \(\quad\)Współautorzy: Armin Fügenschuh, Konstanty Junosza-Szaniawski | ||
| 07.10.2026 | Jakub Żuchowski | PW |
| Listowe kolorowanie grafów uporządkowanych z zabronionymi podgrafami indukowanymi, c.d. | ||
| \(\quad\)Kontynuujemy rozważania na temat problemu listowego kolorowania w klasach grafów uporządkowanych z wykluczonym ustalonym podgrafem indukowanym. Tym razem skupimy się na problemie List-3-Coloring w przypadku, gdy wykluczony wzorzec składa się z dwóch krzyżujących się krawędzi oraz ewentualnych wierzchołków izolowanych. Przedstawimy algorytm quasi-wielomianowy dla tej klasy. Omówimy także związek rozważanej klasy z grafami outerstring. Wyniki uzyskane we współpracy z Pawłem Rafałem Bielińskim, Michałem Dębskim, Martą Piecyk i Pawłem Rzążewskim. | ||