Data wydarzenia:

XXVII Uroczysty Wykład im. Wojtka Pulikowskiego

Wykład pt. "Grafy bez długich indukowanych ścieżek"

wygłosi dr hab. Marcin Pilipczuk z Wydziału Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

Streszczenie wykładu:

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.