On-line Ramsey numbers of paths and cycles (Q490318)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On-line Ramsey numbers of paths and cycles |
scientific article |
Statements
On-line Ramsey numbers of paths and cycles (English)
0 references
22 January 2015
0 references
Summary: Consider a game played on the edge set of the infinite clique by two players, Builder and Painter. In each round, Builder chooses an edge and Painter colours it red or blue. Builder wins by creating either a red copy of \(G\) or a blue copy of \(H\) for some fixed graphs \(G\) and \(H\). The minimum number of rounds within which Builder can win, assuming both players play perfectly, is the on-line Ramsey number \(\tilde{r}(G,H)\). In this paper, we consider the case where \(G\) is a path \(P_k\). We prove that \(\tilde{r}(P_3,P_{\ell+1}) = \lceil 5\ell/4\rceil = \tilde{r}(P_3,C_{\ell})\) for all \(\ell \geq 5\), and determine \(\tilde{r}(P_4,P_{\ell+1})\) up to an additive constant for all \(\ell \geq 3\). We also prove some general lower bounds for on-line Ramsey numbers of the form \(\tilde{r}(P_{k+1},H)\).
0 references
on-line Ramsey theory
0 references
combinatorial games
0 references
paths
0 references
cycles
0 references