Matyáš

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.

Organizace / Geometrické Ramseyovo číslo

2018-10-10
Schůze Radovan v pátek po cviku TGR Morassovi je to jedno, hlavně ať se sejdeme my Vašek může celé odpo pátek (většinou) Štěpán může celé odpo pátek Tung může celé odpo pátek (místo práce) Matyáš učí do 14:15 Pepa nevíme Šimon pracuje Brali jsme opět Geometrické Ramseyovo číslo. Připoměli jsme si závěry z Tomášovi přednášky na STIGMě a zkoušeli jsme neúspěšné rekonstruovat důkaz pro cesty na konvexní množině bodů.

Eternal Domination

2018-08-08
Téma bylo Eternal domination, popis řešení přes stromový rozklad, které je ale stále exponenciální ve velikosti vstupu. Model, kde na grafu je k obránců a přichází naráz k útoků. Třídu grafů, pro kterou je v tomto modelu možné ubránit libovolnou posloupnost útoků, lze definovat pomocí zakázaných antigrafů. Pro k ochránců a graf G jsou doplňku G’ zakázené jako podgrafy $K_{1,k}, K_{2,k-1}, \dots, K_{\lfloor k/2 \rfloor,\lceil k/2 \rceil}$.

Eternal Domination

2018-08-08
Dnes mluvil Matyáš na téma Eternal Domination. Zmínila se jeho bakalářka a její výsledky. Ukázala se strategie pro stromy. Diskutovalo se o DP řešení na stromech a jak (a jestli) je rozšířit na stromový rozklad (PAMový). Problém je, že závislost mezi přechody DP nemusí záviset pouze na sousedech v rozkladu. Rozklad grafu na úplňáky a hvězdy není úplně cesta, protože braní hvězd na kružnici přidá jenom 1 guarda, zatímco skutečné hvězdy se brání 2 guardy.

Ustanovující schůze

2018-08-08
nástřel témátek - 1x měsíčně nastřelit 2 témata řešitelské semináře 1x týdně Pátek 12:00-14:00 představí se otevřený problém (případně i s trochou teorie) a bude se nad ním skupinově sedět založit formální výzkumnou skupinu -> pizza domluvené přednášky/workshopiky - příležitostně (měsíčně?) další ustanovující schůze cca 1x měsíčně (později třeba řidčeji) bylo odhlasováno, že bude ŘS v Pátek 12:00 Štěpán ukáže problém paralelního mergování Matyáš ukáže eternal domination VALHALLA výzkumná akademická algoritmická a letní logická laboratorní lumíci lukrativní heuristiky homomorfismy