Hamburg University of Technology / Institute of Mathematics / Research Topics / Research Topic: Maker-Breaker games on random graphs German flag

Research Topic: Maker-Breaker games on random graphs

Working Groups: Chair Discrete Mathematics

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

Collaborators (External): Pranshu Gupta, 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.

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 probability \(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\).


[CHMP2020] D. Clemens, F. Hamann, Y. Mogge, and Olaf Parczyk, Positional games on randomly perturbed graphs, arXiv:2009.14583 (2020)