Strong Ramsey games: Drawing on an infinite board

摘要

Consider the following strong Ramsey game. Two players take turns in claiming a previously unclaimed edge of the complete graph on n vertices until all edges have been claimed. The first player to build a copy of K-q (q >= 3) is declared the winner of the game. If none of the players win, then the game ends in a draw. A simple strategy stealing argument shows that the second player cannot expect to ever win this game. Moreover, for sufficiently large n, it folloWs from Ramsey's Theorem that the game cannot end in a draw and is thus a first player win. A famous question of Beck asks whether the minimum number of moves needed for the first player to win this game on K-n grows with n. This seems unlikely but is still wide open. A striking equivalent formulation of this question is whether the same game played on the infinite complete graph is a first player win or a draw.