Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Two variants of the size Ramsey number

100%

Kurek A., Ruciński A.

Discussiones Mathematicae Graph Theory

2005

tom 25

nr 1-2

141-149

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

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Kurek A.

1 Ruciński A.

1 2005

Wyniki wyszukiwania

Two variants of the size Ramsey number