A Constructive Winning Maker Strategy in the Maker-Breaker $C_4$-Game

Abstract

Maker-Breaker subgraph games are among the most famous combinatorial games. For given $n,q\in \mathbb{N}$ and a subgraph $C$ of the complete graph $K_n$, the two players, called Maker and Breaker, alternately claim edges of $K_n$. In each round of the game Maker claims one edge and Breaker is allowed to claim up to $q$ edges. If Maker is able to claim all edges of a copy of $C$, he wins the game. Otherwise Breaker wins. In this work we introduce the first constructive strategy for Maker for the $C_4$-Maker-Breaker game and show that he can win the game if $q<0.16 n^{2/3}$. According to the theorem of Bednarska and Łuczak (2000) $n^{2/3}$ is asymptotically optimal for this game, but the constant given there for a random Maker strategy is magnitudes apart from our constant $0.16$.