Geometrické Ramseyovo číslo

Materiály

Okrajově

Teorie

Obecně Ramseyovky jsou o: máme graf G a třídu grafů F, existuje graf 2-hranově obarvený $f \in F$ takový, že vždy obsahuje monochromatickou kopii G. V geometrických Ramseyovkách $R_g(G)$ máme F třídu všech klik a pro vybranou kliku $K_P$ máme množinu vrcholů v rovině P (|P|=n). Hrany mezi vrcholy P jsou nakreslené úsečkami a jsou 2-obarvené. Cílem potom je ukázat, že graf G je obsažen jako jednobarevný podgraf (nakreslení) $K_P$ tak, že jeho nakreslení mezi vrcholy P je bez křížení hran. Zajímá nás n co nejmenší.

Convex geometric Ramsey number $R_c(G)$ – jako GRN, ale vrcholy P jsou na své konvexní obálce.

  • Károly, Pach, Toth - v $K_P$ obsahuje jednobarevnou kostru kde se žádné hrany neprotínají.
  • Valtr - $K_P$ má $C_3, \dots C_{\lceil\sqrt{n/2}\rceil}$.
  • $R_{g,c}(G) < \infty \Leftrightarrow G \text{ je outerplanar}$ (aplikace Ramseyovky, a cv1)
  • Schelps $R(\text{outerplanar}) = O(n)$
  • $R_c(G) \leq R_g(G)$
  • $R_c(C_n) = R_g(C_n) = 2(n-2)(n-1)+2$
  • $R_c(P_n) = n^2$ a $R_g(P_n) = n^{3 \over 2}$
  • $R_c(\text{ladder}) \leq 2n^3$ a $R_g(\text{ladder}) \leq O(n^10)$

Cviko

  • cv1 - Outerplanární triangulace G lze vnořit do množiny bodů P v obecné poloze.

Open

  • q1 - $G_g(\text{outerplanar}) \leq poly(n)$ ?
  • q2 - (=>q1) - $G_g(\text{outerplanar}) \leq cn^2$ ?
  • q3 - vylepšit $R_g(P_n)$ ?
  • q4 - $K_P$ obsahuje housenku jako kostru ? (proti cestě je protipříklad)
  • q0 - $R_{c,g}(X,Y)$ kdy chceme červeně X nebo modře Y (zdá se dobrá šance s tím pohnout)
    • umí se housenka vs outerplanar
    • umí se cykly a nějaké speciální outerplanar

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

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

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