Valhalla

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

2018-11-02
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-26
$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).

Geometrické Ramseyovo číslo

2018-10-12
$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-05
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-14
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-07
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

d-Path Vertex Cover

2018-08-31
Dnes pokračoval Radovan na téma d-PVC. Poznámky a pozorování pro d-liche => modra komponenta spojuje nejvice 2 cervenech vrcholy?? => nelze do ni napojit cerveny vrchol, ktery tvori d+1 cestu s obema cervenyma vrcholama => nejsou modre listy => idea s dominovanim = presunuti do cervenych vrcholu + kazdy vrchol je soucasti nejake d-cesty => idea seznamu vzdalenosti modreho vrcholu od jeho cervenych vrcholů => ale pouze kdyz ty cesty k cervenym vrcholum jsou disjunktni => v tom seznamu kazda dvojice musi presne secist na d ?

d-Path Vertex Cover

2018-08-24
Dnes mluvil Radovan na téma d-PVC a hitting set. Hitting set vstup: je dán graf a nějaké podmnožiny V(G) F, kde každé je velké nejvýše d. výstup: vybrat co nejméně vrcholů takových, aby bylo pokryté každé F. d-Path Vertex Cover vstup: graf G, $k \in \mathbb{Z}_0^+$, kde $k$ je velikost řešení výstup: $F \subseteq V(G), |F| \leq k$ tedy G \ F takový, aby neobsahoval cestu na d vrcholech

Eternal Domination

2018-08-10
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-03
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.