Ondra

Pár nesouvisejících problémů a Eternal domination

2018-11-11
Tung ukázal pár drobných problémů, nad kterými jsme strávili chvilku, před tím než přišel Radovan a Ondra, kdy jsme se začli bavit o ED. Koukli jsme na neklikovou strategii na mřížce 5x5. Používá 10 stavů, které jsou ‘skoro’ symetrické. Šlo by nehledat nejmenší strategii, ale nějakou symetrickou.

Geometrické Ramseyovo číslo

2018-10-10
$R_g(P_n,C_3) = 2n+1$ Dolní mez - Mějme dvě červené kliky s N vrcholy s úplným bipartitním grafem mezi. Horní mez - Seřaďme body a nechme aby červené hrany definovaly poset. Potom nejvyšší počet vrcholů kde není antichain velikosti 3 (modrý trojúhelník) či chain s N+1 vrcholy (cesta na N hranách) je 2N. Pokud přidáme jeden vrchol, tak dostaneme jednu z těchto struktur. $2n+1 \le R_g(C_n,C_3) \le 3n+O(1)$ Dolní mez - platí z cestového výsledku.