Twierdzenie o minorach (Aula A)

Łukasz Kamiński (UW)

Minory to intrygujące pojęcie w teorii grafów. Już Kuratowski zauważył, że za ich pomocą można scharakteryzować grafy planarne. Około pół wieku później Robertson i Seymour opublikowali serię prac liczących łącznie ponad 500 stron, która dowiodła daleko idącego uogólnienia twierdzenia Kuratowskiego - tzw. twierdzenie o minorach. W referacie opowiem czym jest WQO, co dokładnie mówi twierdzenie o minorach i jakie ma ono znaczenie dla teorii grafów jak też dla algorytmiki.