A Constructive Winning Maker Strategy in the Maker-Breaker C₄-Game

Maker-Breaker subgraph games are among the most famous combinatorial games. For given n,q ∈ N and a subgraph C of the complete graph Kₙ, the two players, called Maker and Breaker, alternately claim edges of Kₙ. 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₄-Maker-Breaker game and show that he can win the game if q < 0.16 n2/3. According to the theorem of Bednarska and Luczak (2000) n2/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.