2024/05/07 by Matthias Sowa, Anand Srivastav, Sowa, Matthias +1
Computer Science · Social Sciences · #Algorithms and Data Compression #Artificial Intelligence in Games #Combinatorics (math.CO) #Digital Games and Media #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2405.04462
openalex publication_date 2024/05/07 · openalex created_date 2024/05/11 · openalex updated_date 2026/07/28
Maker-Breaker subgraph games are among the most famous combinatorial games. For given n,q ∈ ℕ and a subgraph C of the complete graph Kn, the two players, called Maker and Breaker, alternately claim edges of Kn. 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 C4-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.