The Namer-Claimer game, part 2

Discrete Mathematics, Volume 344, Issue 3, March 2021, 112256 https://doi.org/10.1016/j.disc.2020.112256 arXiv

I’ve previously written about the Namer-Claimer game.  I can now prove that the length of the game is \Theta(\log \log n) with optimal play from each side, matching the greedy lower bound.  The upper bound makes use of randomness, but in a very controlled way.  Analysing a truly random strategy still seems like it will be very difficult.

The proof brings up a surprising connection to the Ramsey theory of Hilbert cubes.

Leave a Reply

Your email address will not be published.