On-Line Ramsey Theory (2004)

Originators: J. Grytczuk, Haluszczak, H.A. Kierstead    (presented by Kevin Milans - REGS 2007)

Definitions: Builder and Painter play a game on graphs. In each round, Builder adds an edge (infinitely many vertices are available), and Painter colors it red or blue. Builder wins by forcing Painter to produce a monochromatic copy of a fixed graph G. Painter wins by forever avoiding that.

Background: The game is closely related to graph Ramsey theory. Ramsey's Theorem guarantees that when n is sufficiently large, every red/blue coloring of the complete graph K_n contains a monochromatic copy of G). The least such n is the Ramsey number R(G).

Without restrictions on the graph Builder presents, Builder thus wins by presenting a sufficiently large complete graph. Hence the rules of the game also specify a graph family H such that after every move the graph that has been built must lie in H. We specify a particular on-line Ramsey game as (G,H).

The freedom that Builder has to respond to Painter's moves makes the problem easier for Builder. The difficulty for Painter is being required to color each edge before seeing later edges; this explains the name "On-Line Ramsey Theory". Several results about on-line Ramsey games appear in [GHK]:

1. Builder wins (G,H) when G is a forest and H is the family of all forests. (This has an easy proof by induction.)
2. Builder wins (G,H) when G is k-colorable and H is the family of all k-colorable graphs. (This is much more difficult and uses the bipartite version of Ramsey's Theorem.)
3. Painter wins (C₃,H) when H is the family of outerplanar graphs.
4. Builder wins (C₃,H) when H is the family of 2-degenerate planar graphs.
5. Builder wins (G,H) when H is the family of planar graphs and G consists of a single cycle plus any set of chords incident to a single vertex.

Conjecture 1: When H is the family of planar graphs, Builder wins (G,H) if and only if G is outerplanar. (It is unknown whether Builder can win on this family for any graph G that is not outerplanar, and it is not known whether Painter can win it for any G that is outerplanar.)

Problem 2: Given a monotone graph parameter ρ, let H_k={G: ρ(G)≤k}. Let f(k) be the minimum m such that Builder wins (G,H_m) whenever G∈H_k. For which graph parameters is it true that f(k) is finite for all k? Determine f(k) for some values of k for some parameter ρ. In particular, is f a bounded function when ρ is "degeneracy".

Comments: Monotonicity for ρ is the property that H_k⊂H_k+1 for all k. Theorem 2 from [GHK] shows that f(k)=k when the parameter is "chromatic number". Theorem 1 from [GHK] shows that f(1)=1 when the parameter is "degeneracy". In general, can Builder force any k-degenerate graph when playing k-degenerate graphs? This scenario also has been studied for ρ= "number of edges" in [GKP] and for ρ= in the 2007 REGS group (see below).

Definition: We use osr(G) to denote the on-line (size) Ramsey number of a graph G, defined to be the minimum m such that Builder can force G by playing in the class of graphs with at most m edges. Simply put, osr(G) is the number of edges Builder may need to play to force Painter to make a monochromatic copy of G when there is no restriction on the edges to be played (other than how many there are.)

Comments: In ordinary Ramsey theory, the size Ramsey number of a graph G is the minimum number of edges in a graph H such that every 2-edge-coloring of H contains a monochromatic copy of G. Clearly osr(G) (defined in [GKP] without putting "size" in the term) is bounded by the size Ramsey number of G. Beck [B] gave a relatively easy proof that osr(K_pp)≥½R(K_p).

Question 3: Is osr(K_p) subquadratic in R(K_p)?

Question 4: Does osr(G) ≥ R(G)/2 hold for all G? For what graphs is osr(G) linear in R(G)? For which graphs can osr(G) be computed?

Comments: Question 3 may be hard, while progress on parts of Question 4 may be easy. Note that osr(K_1,m)=2m-1. [GKP] studied this parameter for paths, trees, and some other graphs. They proved for example that osr(P_n)&le 4n-7, with exact values up to P₆, but also that osr(G) can be quadratic in the number of vertices when G is a tree.

Definition: We use odr(G) to denote the on-line degree Ramsey number of a graph G, defined to be the minimum k such that Builder can force G by playing in the class S_k of graphs with maximum degree at most m.

Comments: The parameter odr(G) was introduced by participants in the 2007 REGS, including Butterfield, Grauman, Kinnersley, Milans, Stocker, and West [BGKMSW]. Results from [BGKMSW] include:

1. odr(G)≤3 if and only if each component of G is a path or each component of G is a subgraph of K_1,3.
2. odr(G)≤2Δ(G)-1 when G is a tree.
3. odr(G)≥Δ(G)-1+max_uv∈E(G)min{d(u),d(v)}
4. odr(C_n)=4 if n is even or at least 689 or equal to 3, and it is always at most 5.
5. odr(G)≤8 if Δ(G)≤2

Question 6: What is odr(C₅)? Does odr(C_n) equal 4 for all n?

Question 7: Can odr(G) be bounded in terms of Δ(G)? (This is a special case of Problem 3.)

Comments: One could also consider games that are easier for Builder by enlarging the target H also to a family; Builder wins by forcing a monochromatic copy of any graph in H. For example, on what families is {C₃,C₄} unavoidable? Other related problems were studied in [B] and [FKRRT].

References:
[B] Beck, J. Achievement games and the probabilistic method. Combinatorics, Paul Erd?? is eighty, Vol. 1, 51--78, Bolyai Soc. Math. Stud., J??os Bolyai Math. Soc., Budapest, 1993.
[FKRRT] Friedgut, E.; Kohayakawa, Y.; R??l, V.; Ruciński, A.; Tetali, P. Ramsey games against a one-armed bandit. Special issue on Ramsey theory. Combin. Probab. Comput. 12 (2003), no. 5-6, 515--545.
[GHK] Grytczuk, J. A.; Hałuszczak, M.; Kierstead, H. A. On-line Ramsey theory. Electron. J. Combin. 11 (2004), no. 1, Research Paper 57, 10 pp. Int. J. Math. Comput. Sci. 1 (2006), no. 1, 117--124.