Online Ramsey Theory Summary

On-line Ramsey Theory for Bounded Degree Graphs

J. Butterfield, T. Grauman, W. B. Kinnersley, K. G. Milans, C. Stocker, D. B. West

Introduce of greedy and consistent painter:
- Greedy ${\cal F}$-painter colors a new edge by red if the resulting red graph lies in ${\cal F}$ (family of graph), otherwise he colors it by blue. The greedy painter is tool for lower bounds.
- The painter strategy is consistent if the color choice for an edge $e$ dependes only on the component where lies the edge $e$. They proved that if the game is played on monotone additive family of graphs, then consistent painter is as strong as any other painter.
Lower and upper bounds for online degree number:
- $R_d(G) \leq 3$ if and only if $G$ is a linear forest or each component lies inside $K_{1,3}$.
- $R_d(G) \geq \Delta(G) + t - 1$, where $t = \max_{\{uv\} \in E(G)} \min\{d(u),d(v)\}$.
- $R_d(G) \leq d_1 + d_2 - 1$, where $d_1$, $d_2$ are two largest vertex degree.
- $4 \leq R_d(C_n) \leq 5$.
- $R_d(G) \leq 6$, when $\Delta(G) \leq 2$.
Download

David Rolnick

David Rolnick

Proved that for tree $T$ is $R_d(T) \leq 4$ if and only if $T$ is maple or $K_{1,4}$.
Maple is a tree with maximum degree 3 and no adjecent vertices have both degree 3.
Download

W. B. Kinnersley, D. B. West

$R_d(T, s) \leq s(\Delta(T) - 1) + 1$, for every tree $T$ ($s$ is a number of colors).
- The inequality is sharp for trees with adjecent vertices of maximum degree.
Computed the upper and lower bounds for $R_d (G_1,\dots,G_s)$, where every $G_i$ is a double-star (tree with a diameter 3).
- In this game painter is forced to paint monochromatic $G_i$ in color $i$ (for arbitrary $i$).
Computed the exactly value of $R_d (G_1,\dots,G_s)$, where every G$G_i$ is a star.
Download

J. A. Grytczuk, M. Halszczak, H. A. Kiersted

Unavoidability - the graph $H$ is unavoidable on a graph class ${\cal C}$, if Builder builds only graphs from ${\cal C}$ and wins the Ramsey game (i.e. painter is forced to draw monochromatic copy of $H$). The class ${\cal C}$ is unavoidable if every graph from ${\cal C}$ is unavoidable on ${\cal C}$.
- $k$-colorable graphs are unavoidable.
- Forests are unavoidable.
- Outerplanar graph are avoidable - painter can avoid a monochromatic triangle on outerplanar graph.
More colors - 3-colorable graphs are unavoidable even painter can use more colors
Download

A. Kurek, A. Ruciński

Mainly about offline Ramsey Number
Online Ramsey theory: $R(3) = 8$ - It suffices (and it is needed) to build 8 edges to force the painter to draw monochromatic triangle (painter uses only 2 colors)
Download

M. Belfrage, T. Mütze, R. Spöhl

Proved that greedy strategy is optimal for painter on some graphs - when target graph is path with 1 - 7 edges.
Proved that greedy strategy (for painter) is not optimal, when targe graph is $P_8$ and found the optimal strategy for painter for this case.
Download

P. Pralat

M. Axenovich, K. Knauer, J. Stumpp, T. Ueckerdt

Studied size and online anti-ramsey numbers for several classes of graphs.
Upper bounds for online anti-ramsey numbers for general graphs, paths, cycles, matching and complete graphs.
Computed first fit anti-ramsey numbers for paths, cycles, matching and complete graphs. First fit anti-ramsey numbers is online anti-ramsey number, when painter use first-fit strategy, so it is lower bound for online anti-ramsey number.
Download

Diploma thesis
Š. Petříčková

Any outerplanar graph containing only cycel of the same parity and no triangles is unavoidable on the class of planar graphs.
$K_{2,3}$ is unavoidable on the class of planar graphs.
Download

J.A. Grytczuk, H.A. Kierstead, P. Pralat

Upper bound for paths: $R(P_n) \leq 4n - 7$.
Upper bound for $R(S_n, H) \leq nm$, where $S_n$ is star with $n$ edges and $H$ is any tree, cycle or clique.
Lower bound for $R(H) \geq \frac{1}{2} c(H)(\Delta(H) - 1) + m$, where $c(H)$ is the size of the minimal vertex cover.
Let $f(n)$ is the maximum value of $R(T)$ taken over all trees with $n$ edges. Proved that $f(n)$ is asymptotically $n^2$.
Download