Data: wtorek, 01.12.2020, godz. 10:00
Prelegent: dr hab. Marcin Pilipczuk (Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego)
Tytuł: Grafy bez długich indukowanych ścieżek
Abstrakt: András Gyárfás w latach 80. ubiegłego wieku zwrócił uwagę na rodziny grafów bez długich ścieżek jako indukowanych podgrafów, dowodząc, że są one chi-ograniczone. Do dziś jednak nie mamy dobrego strukturalnego zrozumienia takich rodzin. Niedawne wyniki pokazują, że główny - i bardzo elegancki - argument z pracy Gyárfása ma również zastosowanie do innych zagadnień, takich jak własność Erdősa–Hajnala czy istnienie efektywnych algorytmów znajdujących największy zbiór niezależny. W czasie wykładu opowiem o niedawnych wynikach w tej dziedzinie i o pytaniach, które wciąż pozostają otwarte.