Seminarium Kombinatoryka, Teoria Grafów i Zbiorów Uporządkowanych
Wydział Matematyki i Nauk Informacyjnych, Politechnika Warszawska
Kalendarz Środy, 10:15-11:45
Pinezka Gmach MiNI PW, Sala 431, ul. Koszykowa 75, Warszawa
Komputer Seminaria odbywają się stacjonarnie z transmisją na platformie MS Teams.
Mail Jeśli chcesz dołączyć do spotkania, to napisz do sekretarza seminarium.

Najbliższy referat
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.
Zespół prowadzący