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

# Research Topic: Maker-Breaker games on random graphs

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

Instead of playing on a complete graph $$K_n$$ we can consider different boards, for example a random graph $$G \sim G_{n,p}$$ with $$n$$ vertices, where each edge is present in the graph with probabality $$p$$. Another option is to consider randomly perturbed graphs, which are the union of a random graph $$G \sim G_{n,p}$$ and a deterministic graph $$G_{\alpha}$$ with minimum degree $$\alpha$$.