On-line Ramsey numbers
| dc.creator | Conlon, David | |
| dc.date | 2009-02-10 | |
| dc.date.accessioned | 2026-07-07T12:39:55Z | |
| dc.date.available | 2026-07-07T12:39:55Z | |
| dc.description | Consider the following game between two players, Builder and Painter. Builder draws edges one at a time and Painter colours them, in either red or blue, as each appears. Builder's aim is to force Painter to draw a monochromatic copy of a fixed graph G. The minimum number of edges which Builder must draw, regardless of Painter's strategy, in order to guarantee that this happens is known as the on-line Ramsey number \tilde{r}(G) of G. Our main result, relating to the conjecture that \tilde{r}(K_t) = o(\binom{r(t)}{2}), is that there exists a constant c > 1 such that \tilde{r}(K_t) \leq c^{-t} \binom{r(t)}{2} for infinitely many values of t. We also prove a more specific upper bound for this number, showing that there exists a constant c such that \tilde{r}(K_t) \leq t^{-c \frac{\log t}{\log \log t}} 4^t. Finally, we prove a new upper bound for the on-line Ramsey number of the complete bipartite graph K_{t,t}. | |
| dc.description | 11 pages | |
| dc.identifier | https://arxiv.org/abs/0902.1715 | |
| dc.identifier | http://arxiv.org/abs/0902.1715 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/219290 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C55 | |
| dc.title | On-line Ramsey numbers | |
| dc.type | text |