On the clique-game

AbstractWe study Maker/Breaker games on the edges of the complete graph, as introduced by Chvátal and Erdős. We show that in the (m:b) game played on KN, the complete graph on N vertices, Maker can achieve a Kq for q=(mlog2(b+1)−o(1))⋅log2N, which partially solves an open problem by Beck. Moreover, we show that in the (1:1) game played on KN for a sufficiently large N, Maker can achieve a Kq in only 22q3poly(q) moves, which improves the previous best bound and answers a question of Beck. Finally, we consider the so called tournament game. A tournament is a directed graph where every pair of vertices is connected by a single directed edge. The tournament game is played on KN. At the beginning, Breaker fixes an arbitrary tournament Tq on q vertices. Maker and Breaker then alternately take turns in claiming an unclaimed edge e and selecting one of the two possible orientations. Maker wins if his graph contains a copy of the goal tournament Tq; otherwise Breaker wins. We show that Maker wins the tournament game on KN with q=(1−o(1))log2N. This supports the random graph intuition, which suggests that the threshold for q is asymptotically the same for the game played by two “clever” players and the game played by two “random” players