On-line Ramsey numbers of paths and cycles

zbMATH Open1305.05138arXiv1404.3894MaRDI QIDQ490318FDOQ490318

Allan Lo, Joanna Cyman, Tomasz Dzido, John Lapinskas

Publication date: 22 January 2015

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: 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

i l d e r (G, H)

. In this paper, we consider the case where

G

is a path

P_{k}

. We prove that

i l d e r (P_{3}, P_{e l l + 1}) = l c e i l 5 e l l / 4 c e i l = i l d e r (P_{3}, C_{e} l l)

for all

e l l g e 5

, and determine

i l d e r (P_{4}, P_{e l l + 1}

) up to an additive constant for all

e l l g e 3

. We also prove some general lower bounds for on-line Ramsey numbers of the form

i l d e r (P_{k + 1}, H)

.

Full work available at URL: https://arxiv.org/abs/1404.3894

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

paths combinatorial games cycles on-line Ramsey theory

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Combinatorial games (91A46)

Cites Work

Cited In (16)

   Recommendations

This page was built for publication: On-line Ramsey numbers of paths and cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q490318)