Radovan

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

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

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