Morass

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
$2n+1 \le R_g(C_n,C_3) \le 3n-3$ Dopočítali jsme přesně mez z minulého setkání a snažili se o její zlepšení. Pozorování: Modrý stupeň je menší jak N jinak bude červená klika na koncích této hvězdy tvořit cyklus (vybereme bod v hull a obtočíme kolem dokola, spojíme sousední -> cykl). Takže pokud máme ~2N+1 vrcholů, tedy 2N kolem jednoho, tak nemůže být N modrých. Máme tedy alespoň N+1 červených kde z každého modrého do nich vedou alespoň 2 hrany (kvůli jejich modrému stupni).

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ů.

Geometrické Ramseyovo číslo

2018-09-09
Pokračovali jsme v tématu z minula. dokázali jsme planární monocolored spanning tree pro konvexní množinu bodů zkoušeli jsme pro nekonvexní, ale bez úspěchu

Geometrické Ramseyovo číslo

2018-09-09
Tomáš nám pověděl základy GRN (vizte soupis v tématu). Zkoumání zkoušeli jsme rekonstruovat důkázek planárního monocolored spanning tree

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