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$.
@article{10_37236_13003,
author = {Matthias Sowa and Anand Srivastav},
title = {A constructive winning maker strategy in the maker-breaker {\(C_4\)-game}},
journal = {The electronic journal of combinatorics},
year = {2025},
volume = {32},
number = {1},
doi = {10.37236/13003},
zbl = {1556.05107},
url = {http://geodesic.mathdoc.fr/articles/10.37236/13003/}
}
TY - JOUR
AU - Matthias Sowa
AU - Anand Srivastav
TI - A constructive winning maker strategy in the maker-breaker \(C_4\)-game
JO - The electronic journal of combinatorics
PY - 2025
VL - 32
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/13003/
DO - 10.37236/13003
ID - 10_37236_13003
ER -
%0 Journal Article
%A Matthias Sowa
%A Anand Srivastav
%T A constructive winning maker strategy in the maker-breaker \(C_4\)-game
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/13003/
%R 10.37236/13003
%F 10_37236_13003
Matthias Sowa; Anand Srivastav. A constructive winning maker strategy in the maker-breaker \(C_4\)-game. The electronic journal of combinatorics, Tome 32 (2025) no. 1. doi: 10.37236/13003
