Two variants of the size Ramsey number

Kurek, Andrzej ; Ruciński, Andrzej

Discussiones Mathematicae. Graph Theory, Tome 25 (2005) no. 1-2, pp. 141-149

Résumé

Given a graph H and an integer r ≥ 2, let G → (H,r) denote the Ramsey property of a graph G, that is, every r-coloring of the edges of G results in a monochromatic copy of H. Further, let m(G) = max_F ⊆ G|E(F)|/|V(F)| and define the Ramsey density m_inf(H,r) as the infimum of m(G) over all graphs G such that G → (H,r). In the first part of this paper we show that when H is a complete graph Kₖ on k vertices, then m_inf(H,r) = (R-1)/2, where R = R(k;r) is the classical Ramsey number. As a corollary we derive a new proof of the result credited to Chvatál that the size Ramsey number for Kₖ equals R2. We also study an on-line version of the size Ramsey number, related to the following two-person game: Painter colors on-line the edges provided by Builder, and Painter's goal is to avoid a monochromatic copy of Kₖ. The on-line Ramsey number R̅(k;r) is the smallest number of moves (edges) in which Builder can force Painter to lose if r colors are available. We show that R̅(3;2) = 8 and R̅(k;2) ≤ 2k2k-2k-1, but leave unanswered the question if R̅(k;2) = o(R²(k;2)).

Détail

Keywords: size Ramsey number, graph density, online Ramsey games