- Tytuł:
- Two variants of the size Ramsey number
- Autorzy:
-
Kurek, Andrzej
Ruciński, Andrzej - Powiązania:
- https://bibliotekanauki.pl/articles/744322.pdf
- Data publikacji:
- 2005
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
size Ramsey number
graph density
online Ramsey games - Opis:
- 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 $\binom{R} {2}$. 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) ≤ 2k\binom{2k-2} {k-1}$, but leave unanswered the question if R̅(k;2) = o(R²(k;2)).
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2005, 25, 1-2; 141-149
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł