Hamburg University of Technology / Institute of Mathematics / Research Topics / Research Topic: Maker-Breaker games with restrictions German flag

Research Topic: Maker-Breaker games with restrictions

Working Groups: Chair Discrete Mathematics

Collaborators (MAT): Dr. Dennis Clemens, Fabian Hamann, M. Sc., Yannick Mogge, M. Sc.

Collaborators (External): Pranshu Gupta, Laurin Kirsch

Description

Biased Maker-Breaker games are played on some hypergraph \((X,\mathcal{F})\), where \(\mathcal{F}\) denotes the family of winning sets. For some biases \(m,b\), during each round of such a game Maker claims (up to) \(m\) elements of \(X\), followed by Breaker claiming (up to) \(b\) elements. If Maker is able to claim all elements of a winning set, she wins the game, otherwise Breaker is declared the winner.

An interesting question to consider is how these games play out, if we restrict Maker’s (and maybe also Breaker’s) moves. For example, we play on a graph \(G\) and allow Maker to only claim edges incident to previously claimed edges by her. These games are called Connector-Breaker games and were first introduced by London and Pluhár [LP2018] under the name PrimMaker-Breaker games. Another variant is to have Maker only claim edges according to a walk. This variant, called Walker-Breaker game, appeared first in a publication by Espig, Frieze, Krivelevich, and Pegden [EFKP2015]. These restrictions lead to interesting new strategies to be considered for both players to enforce a win.

Additionally one can also add restrictions to the board we play on, for example instead of playing on the complete graph \(K_n\) we will play on random graphs \(G \sim G_{n,p}\) with \(n\) vertices, where each edge is contained in the graph with probability \(p\). Here, a typical goal is to find the threshold probability \(p^*\), where a Maker’s (Connector’s/Walker’s) win turns into a Breaker’s win.

References

[CKM2019] D. Clemens, L. Kirsch, and Y. Mogge. Connector-Breaker games on random boards, arXiv:1911.01724 (2019), accepted for publication in Electron. J. Combin.

[CT2016] D. Clemens and T. Tran. Creating cycles in Walker-Breaker games, Discrete Mathematics Volume 339, Issue 8, August 2016, 2113–2126.

[EFKP2015] L. Espig, A. Frieze, M. Krivelevich, and W. Pegden. Walker-Breaker Games, SIAM J. Discrete Math., 29(3), 1476–1485.

[LP2018] A. London and A. Pluhár. Spanning Tree Game as Prim Would Have Played, Acta Cybernetica, 23(3), 921–927.