TUHH / Institut für Mathematik / Forschungsgebiete / Research Topic: Maker-Breaker games with restrictions

# Research Topic: Maker-Breaker games with restrictions

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