On the clique-game

We 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)(m:b) game played on KNKN, the complete graph on NN vertices, Maker can achieve a KqKq for q=(mlog2(b+1)−o(1))⋅log2N, which partially solves an open problem by Beck. Moreover, we show that in the (1:1)(1:1) game played on KNKN for a sufficiently large NN, Maker can achieve a KqKq 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 KNKN. At the beginning, Breaker fixes an arbitrary tournament TqTq on qq vertices. Maker and Breaker then alternately take turns in claiming an unclaimed edge ee and selecting one of the two possible orientations. Maker wins if his graph contains a copy of the goal tournament TqTq; otherwise Breaker wins. We show that Maker wins the tournament game on KNKN with q=(1−o(1))log2Nq=(1−o(1))log2N. This supports the random graph intuition, which suggests that the threshold for qq is asymptotically the same for the game played by two “clever” players and the game played by two “random” players.