Tung

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.

d-Path Vertex Cover

2018-08-08
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-08
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-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