arXiv SIDMA | tags:[ combinatorial games ]
Online Ramsey numbers: Long versus short cycles
with Grzegorz Adamski and Małgorzata Bednarska-BzdęgaIn Online Ramsey games we have two players. One is placing edges to a graph with infinite number of vertices while the second chooses their color to be blue or red immediately. Builder (the first player) aims to force a monochromatic graph to appear. Painter (the second player) tries to postpone win of the first player as long as possible. Due to Ramsey theorem, we know that the first player eventually wins. Our aim is to analyze the game to determine the minimum number of rounds necessary for the first player win.
In my previous work we found out that if the target graph is a cycle then we can build it in linear time (with a reasonable constant), even if the target graph has to appear as an induced monochromatic subgraph.
In this work, we looked at the case where as the target we can either obtain a long red cycle or a short blue cycle. The short cycle is negligible in size when compared ot the long one, so we focus on approaches that optimize multiplicative constant in term of the long cycle. We get an optimum 2 for even-long cycles and we get close to a known lower bound for odd-long cycles.