Research Topic: Maker-Breaker games with restrictions
Working Groups: Lehrstuhl Diskrete Mathematik
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.
