Data wydarzenia:

Wariant online krawędziowej liczby Ramseya i złoty podział

Data: wtorek, 19.10. 2021, godz. 10:00-10:55

Prelegent: mgr Grzegorz Adamski (WMiI UAM)

Miejsce: aula B

Abstrakt: Rozważmy grę, w której jest dwóch graczy, konstruktor i malarz. W każdej turze konstruktor wybiera krawędź z nieskończonej kliki K_N. Następnie malarz koloruje ją na niebiesko bądź na czerwono. Gra kończy się w momencie, gdy pojawi się kopia grafu należącego do ustalonej rodziny „zakazanych” dwukolorowych grafów F. Celem konstruktora jest zminimalizowanie liczby ruchów, a celem malarza jest jej zmaksymalizowanie. Krawędziową liczbą Ramseya w wersji online nazywamy liczbę r̃(F) tur w grze, w której obaj gracze grają optymalnie.
Zaprezentuję oszacowania tych liczb dla przypadków, gdy F składa się z czerwonej ścieżki C_k i niebieskiej ścieżki P_n dla k=3,4.