TUHH / Institut für Mathematik / Forschungsgebiete / Research Topic: Maker-Breaker games with restrictions on random graphs Englische Flagge

Research Topic: Maker-Breaker games with restrictions on random graphs

Working Groups: Lehrstuhl Diskrete Mathematik

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

Collaborators (External): Laurin Kirsch


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. Such a game we call Connector-Breaker game. Another example is to have Maker only claim edges according to a walk. This variant we call Walker-Breaker game. These restrictions lead to interesting new strategies to be considered for both players to enforce a win.

Additionally let us restrict the board we play on. For this 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 probabality \(p\). 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.


[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.